Can I do this on a 4GB SDHC card or does it have to be only SD?
You can do this on SD and SDHC memory cards, only the file system matters (the camera hardware must support SDHC cards, of course).
There's only one condition for the automatic loading mechanism with a locked, prepared card (CHDK-bootable with the "BOOTDISK" signature at offest 40h): the first partition on the memory card must be FAT12 or FAT16 formatted; this is caused by the Canon firmware update mechanism which we are (ab)using to load the CHDK code.
FAT16 is limited to a partition size of 4GB.
--> you can use a 4 GB SD or SDHC card with one FAT16-formatted partition,
--> you can use a multi partition setup (with a small FAT12/FAT16 partition + a big "data" partition in FAT32 format),
--> you can also use a card > 4 GB with a single FAT16 formatted partition on it, up to 4 GB of size.