Themes manage the display and layout of your blog, but can also add functionality.
Plug-ins add functionality to your blog, but can also add elements to the layout.
There is a lot of crossover between the two, particularly when you being to bundle certain plug-ins with themes. However, the biggest difference lies in the templates your site uses.
Themes
Themes define the templates used for each page. In general, index.php in a theme is used for just about everything. You can split that out and create a separate header.php and footer.php as well. Then you can add a sidebar.php. I’m sure you’ve seen at least these four files before – one to define the header, one to define the sidebar, one to define the footer, and one to bring them all together and position them around the main content.
Further, you can define single.php to style a single post, page.php to style individual pages, and so on.
When your site loads and a page or post is requested, WordPress routes the request to the template file defined by your theme. Then it knows how to lay things out on the page. Traditionally, themes are just for layout.
Plug-ins
Plug-ins, on the other hand, can add additional elements to be used by the themes and elsewhere. A plug-in can add a Facebook Like button that your theme can then add to posts and pages. Another plug-in can add a widget to your admin dashboard for accessing and managing your Google Reader feed – this is not reflected in the layout of your site, but does add functionality. Yet another plug-in can automatically post to Twitter whenever you publish a new post.
Themes can add functionality that is directly related to the layout and performance of your site. Plug-ins can add functionality deeper in WordPress – functionality that can also be used by a theme.