Okay, here's what I figured out.
This page solved my issue for me.
Essentially, I have a single HTML document that contains my entire ebook that I want to construct. It has an HTML ToC that I coded by hand (well, I used a script to generate it, but shh). I use the perl tool html2mobi (mobiperl) to turn my HTML files into PRC files (which as I understand it are essentially MOBI files). html2mobi lets me attach metadata (author, title, etc.) using command-line options, but I didn't know how to make it recognize a ToC entry.
So I added more or less the same thing Jeff L posted (the guide/reference tags) into the HEAD tag of my HTML doc:
<guide>
<reference type="toc" title="Table of Contents" href="#toc">
</reference>
</guide>
...and then added an A tag like so:
<a name="toc">Contents</a>
...around the word "Contents" at the top of my ToC. That was all I had todo; html2mobi recognized it and now the "Table of Contents" menu option works in both my Kindle 3 and Kindle for Android.
Here's hoping the next person to want to do this doesn't have the same problem. I wish Amazon's Kindle formatting documentation was less awful.