As said by others, external hard drive (or another computer's hard drive), and make sure you keep the backup copy in another room than the main copy, out of reach of flooding, don't leave it plugged in to protect from power surges, etc. Also keep a third copy around of the really important stuff (passwords, legal stuff, address book...), in another building if you can (but beware of possible theft, of course). Don't update this third copy as often nor at the same time as the other backup, just in case your backup process accidentally corrupts the backup, so you don't destroy both backups at once.

CD-R(W)s and DVD-R(W)s are generally considered no good for long term storage, because they can degrade over the course of a few years. Of course, hard drives do too, but they tell you so, so you can replace the hard drive before you loose the data.

Paranoia ? No, all this learned from personal experience.