Your question is good and often asked in the Joomla world. I will write a blog post about it soon. Until then:
1. You site doesn't have to be down any time, you can switch template instantly
2. You have to understand what are the elements of Joomla template:
a) MODULE POSITIONS: In example, you have old template with module positions 'user1' (header), 'left' (left column), 'right' (right column) and 'bottom' (footer area). Now, you are replacing it with new template, with module positions 'top' (header), 'left' (left column), 'right' (right column) and 'footer' (footer area). In this example, after template switching, you should change module positions of all your 'user3' and 'bottom' modules to 'top' and 'footer'
b) MENUS: Usually, in Joomla we have top (horizontal) menu with or without drop-downs and vertical menu (left or right column). In our templates, drop-down top menu is usually on position 'user3' (anyway, check module positions for each template in template demo) and settings should be as per
The vertical menus shouldn't have any module class suffix in menu module parameters
c) CONTENT PAGES: If your content pages are created per standards and without tables, move to the new template will be straightforward and you probably wouldn't need any page edits. However, if you have content pages with tables that has widths set, you would maybe need to edit the table widths (enlarge or reduce it) to fit new template. However, our templates are flexible and for any template (except ItStarts) you can change width of main area and left/right columns.
d) OTHER: There may be additional things you should edit to fit the new template. Additional extensions (components and module) may need tweaks. For straightforward sites, template switch is usually easy, but as site is more and more complex (more elements, extensions, module positions, pages…), template switch is more and more complex. It's always possible, but complex sites it may require more time and more Joomla knowledge.