After downloading the ubuntu-12.04-desktop-amd64.iso nautilus listed its size as 732.2 MB. It's supposed to be 698 MB according to the release page, yet the sha256sum came out exact. What's up with that?

The exact size in bytes is 732213248. This is a little over 698 * 1024 * 1024, or a little over 732.2 * 1000 * 1000. The web server shows sizes in the kind of megabyte that's 1024 * 1024 bytes (sometimes called "mebibyte" or MiB), while Nautilus shows sizes in the kind of megabyte that's 1000 * 1000 bytes. Both variants are used by hardware manufacturers in different contexts (RAM, disk, network, etc.), and so you'll see sizes quoted in one or the other unit in various places. This isn't ideal, but we're kind of stuck with it one way or the other.

In any case, this is a good old-fashioned matter of units, and doesn't represent a problem with the image you've downloaded.

There's no need to check the MD5sum, as you've already checked the (stronger) SHA256sum.