The first thing you need to do is create a sitemap.xml file. This is really easy to do automatically in MovableType by creating a custom index template. Go into Design - Templates - Index Template. Create a new template called "Sitemap." Set the following options:
Output File: sitemap.xml
Template Type: Custom Index Template
Link to File: (leave blank)
Publishing: Statically (the default)
Then you just need to create the template. Here's the one I use for the tech blog:
Here's what I used on my food blog:
This is a little more complicated because any entries that are tagged "whatiate" have a lower priority than other pages. In other words, pages that are not tagged "whatiate" will almost always appear higher on the search results within my page.
When you publish the site, the sitemap.xml file should be created in the top level of the blog. A good start!
Next edit your robots.txt to block search engines from accessing the /cgi-bin directory. You might just block /cgi-bin/mt/mt-search.cgi, but it was fine for me to block everything. This is useful because sometimes people will link to a search page instead of an actual page, and this really bogs down the server for a large blog.
Also note that robots.txt now references the sitemap file. This will help other search engines find it.
Finally, in the case of Google, go to the webmaster tools and submit the URL to your sitemap.xml file. Within a few days Google will hopefully index your site properly.
The second part of this is is to create a Custom Google Search engine. This is pretty self-explanatory - follow the steps and it will spit out a little block of html you can insert into a page and that's it. You can see this in action in my food blog custom search page. The Google search is so much better than the MovableType search. Not only is it faster, but its ranking works much better than MovableType's does.