Key structural elements

Core HTML(4) structural elements

These are built into HTML and already have good support from screen readers and other assistive technologies:

Headings
Headings, levels 1-6 (<H1> - <H6>) are used to label content on the page, and screen readers use them to navigate within a page.
NB: HTML5 has defined a different way of dealing with headings, but the spec is not settled on that point and current technology still uses HTML4 style headings.
Lists
Ordered (ol) and un-ordered (ul) lists are used to group things like navigation items and bulleted lists.
Tables
Tables should be used for tabular data, where the relationship between headings and cells matter. (Like the checklist.)

ARIA landmark roles

The Accessible Rich Internet Application specification (ARIA spec) has a section dedicated to landmarks, attributes that you apply to HTML elements. For example:

<form action="/search" method="get" role="search">

These provide extra hooks for assistive technology to use in navigating pages and applications. Current support is good in some screen readers (e.g. last few versions of Jaws, and recent NVDA and VoiceOver versions). However, keyboard users have no means of accessing them yet.

Banner
A region that contains mostly site-oriented content, rather than page-specific content. Typically you would apply this to the top area of each page that includes the logo & site search.
You would generally only have one banner.
Main
The main content of a document. Generally this would be the target of the 'skip to content' link.
You must only have one main.
Complementatary
A supporting section of the document, designed to be complementary to the main content at a similar level in the DOM hierarchy, but remains meaningful when separated from the main content.
Contentinfo
A large perceivable region that contains information about the parent document. Examples of information included in this region of the page are copyrights and links to privacy statements.
Basically this is for the footer.
Navigation
A collection of navigational elements (usually links) for navigating the document or related documents.
There can be more than one navigation.
Search
A landmark region that contains a collection of items and objects that, as a whole, combine to create a search facility.

There is a complete list in the specification, but please make sure you know what impact the other ones have before using them.

HTML5 introduces some new elements, some of which map to landmarks. However, support is not as good for those yet. Use them as per the HTML5 spec, but don't assume that assitive technology is doing anything with them yet.

Article
a complete, or self-contained, composition in a document, page, application, or site and that is, in principle, independently distributable or reusable, e.g. in syndication. This could be a forum post, a magazine or newspaper article, a blog entry, a user-submitted comment, an interactive widget or gadget, or any other independent item of content.
Don't over do it!
Aside
a section of a page that consists of content that is tangentially related to the content around the aside element, and which could be considered separate from that content. Such sections are often represented as sidebars in printed typography.
Footer
a footer for its nearest ancestor sectioning content or sectioning root element. A footer typically contains information about its section such as who wrote it, links to related documents, copyright data, and the like.
There can be many footers on a page if there are many articles.
Header
introductory content for its nearest ancestor sectioning content or sectioning root element. A header typically contains a group of introductory or navigational aids.
Nav
a section of a page that links to other pages or to parts within the page: a section with navigation links.
Section
a generic section of a document or application. A section, in this context, is a thematic grouping of content, typically with a heading.
Please note that a section != div! I'm not entirely sure what impact it is supposed to have on assistive technology, but at the moment Jaws will announce it every time you get to one.

More on the screen reader support at Tink.co.uk and HTML5 accessibility.

For the landmarks which can be used more than once on a page, it can help to label them.

For example, if you had this navigation element:

<nav role="navigation">
<p>Choose an aisle to browse:</p>
<ul>
<li><a href="fresh.html">Fresh foods</a></li>
<li><a href="dairy.html">Milk and dairy</a></li>
…
</ul>
</nav>

You could provide a label for that navigation:

<nav role="navigation" aria-labelledby="firstLabel">
<p>Choose an <span id="firstLabel">aisle</span> to browse:</p>
<ul>
<li><a href="fresh.html">Fresh foods</a></li>
<li><a href="dairy.html">Milk and dairy</a></li>
…
</ul>
</nav>

(Example borrowed from Tink.co.uk).