Are you making it to sell it? Or for your personal use?

If you're using it personally I would just install the All In One SEO plugin and you're set

I do that normally, but I'm making this theme to sell. I guess I could program something like All in One SEO directly into the theme? Is there any SEO things that are related to the structure of the page or anything like that?

Normally plugins like WP SEO will add this for you but you could always put the meta code into your theme directly.

WordPress themes are already optimised "out of the box" for search engines. I personally haven't seen any difference in SERPs by using a specific theme. I generally make sure that the website theme is "clean" and the content is red hot. That's enough for conversions.

Make a SEO audit of your template using free seoptimer.com - don't forget to check post pages, archives, categories etc.

There are many free WP plugins that can help you do that. I also know there are paid (and better?) plugins. Coming to think of it i'll check it out too

Wow nothing like a spammer - nice anchor text on your links.....

NOW To answer the question.

There is on-page SEO and off-page SEO. You are referring to the on-page SEO based on the question you are asking.

The site SEO is taken care of in Wordpress under "Settings" and "General" be sure the site title contains your keywords.

Also under "Settings" if you install the All-In-One SEO plug-in select that on the Settings menu. You have the ability to add you site title, description, keywords etc. for the site.

All-In-One also supports and helps you on each individual blog post or page or your site as well. Fill in the info at the bottom of the post or page for the All-In-One plug-in.

I also use SEOPressor when I write the posts or pages to be sure I'm fully optimized for the title, h1, h2, keyword density etc.

What do you want to "optimize". Wordpress themes all give you titles and tags and a box to put your text into. That's what google sees.

To mix things up on a post-by-post basis, use a plugin like Yoast SEO, but for the main, just let your theme ride.

There's a lot to SEO - too much to write out here. You're going to want to make sure you have the basics built in like the ability for users to create the titles of their pages, meta-descriptions, etc. of course, but your best bet is probably either to 1) copy Elegant Themes or WooThemes or one a provider who had SEO already built in or better yet, 2) Save yourself a LOT of time by just making integration with Yoast SEO simple.

I agree with intergen on the All in One SEO plugin - while I've used SEOPressor, Yoast and Clickbump it seems I always revert back to All in One.

Great SEO audit link, xradar.