What is the relationship between regions and panels?
Panels can be thought of as self contained themes you define within a specific Drupal Theme displaying the page.  Like Drupal themes, panels also contain regions, but you define them, rather than the default theme.  

And to expand upon this a bit more:

Panels presents a way to display content similar to a theme, but in a more modular fashion.   This site gives an excellent example of how panels can be used. A mini-panel, for instance, is used similarly to a  block and can, in fact, be placed in a region of a theme just like blocks are.  The advantage is that a panel/mini-panel can contain its own layout regions further breaking down the layout.  For instance, the signature blocks in this Drupal Answers question layout contains the top line with how long ago the question was asked, the avatar, authors site name and reputation.  Using mini-panels this configuration could be defined as a single mini-panel and placed inside a larger panel that holds other mini-blocks laying out the arrows and other graphics at the left side, the actual question, the tags and the action links such as links, edit, etc.  

This larger panel construct can also be placed within a theme region such as the 'content' area giving the site display you see for your question page. Other content such as a list of the answers to your question can also be added to the main content area. Other regions such as right sidebar can hold the related questions links.  In this way your panels are placed within the existing theme framework providing additional content layout flexibilities.

Panels can be laid out in prearranged formats or be user designed as custom layouts.  These panel layouts contain their own regions so you are in-essence adding regions within a theme regions.

Panels can also go one step further and totally replace the theme layout using the Panels Everywhere module.  This offers the user the ability to control the layout and styles directly.  While contributed themes can be very flexible and sophisticated, these very capabilities can also make them very complex and difficult to modify to meet individual project demands.  The more experienced you become in using Drupal, the more attractive this ability may become for you.

Panels also offer another advantage.  The panels module works very well with CTools Page Manager, joining graphic control with Page Manager's content control.  In this way you can intercept URL requests before Drupal responds and set rules and layouts to respond to various context conditions using 'Variants'.  IN this way you can vary the content depending upon the permission levels of a user, or the content type being requested.  If specific conditions are not met, then panels/page manager, returns display control back to Drupal.  In addition, panels can display views and even pass its context to the view to determine what the view will show.  All of this gives the designer the control necessary to duplicate the content and layout this site provides.