The hard drive can be replaced without voiding the warranty if it is done by an Apple certified resller, just not by the user. I believe it used to be consider user-replaceable on the Ti-Book, however. It is definitely not something to be undertaken unless you are very comfortable disassembling your powerbook.
Anyway, if you really want to upgrade the hard drive yourself, you might consider waiting a few months until 7,200 RPM 80GB drives become available from Hitachi and Seagate.