Yes if you remove the hard drive then no-one will be able to recover anything from the laptop.
So you could do what you are suggesting.
Changing the hard drive is quite easy just disconnect the old one and then attach the new one.
A new hard drive would need to be formatted (probably NTFS) and have Windows reinstalled from the original CD (if you plan to pass on the operating system with the laptop). If it's XP or Vista the Windows setup cd should format the drive for you.