Yes, just about any IDE/ATA drive will be fine.
Just that simple also
If so, is it as simple as switching the drives, starting the machine from OS X CD and then frantically waving a magic wand around?
I'd presumably install the system onto my 'new' disk from the CD, then copy my installation files (and re-install applications) and data files to the 'new' disk?
Yes to that also.
Would I make a clone (using Carbon Copy Cloner?) onto an external HD, format the 'new' disk and then do a sort of reverse-clone from the external to the 'new' disk?
Yes to that also - but my choice would be to install everything from disks.