SD or SDHC; write speed really doesn't matter, as I've found that even the cheapest cards can keep up with the Canon's video mode.
I believe pretty much any card over 2GB is SDHC these days. The speeds are classified differently. For regular SD, you typically see them advertised as 60x or 133x or something-x. For SDHC, they are classified by Class-4, Class-6, Class-x. The higher the class, the faster the card.
4GB cards are under $20; 8GB under $40. Bigger capacity can come in handy if you plan on recording video often.