This is the first question you have to ask yourself.
Here are some of the pros and cons of a clean install:
Clean Install pros
Clean Install cons
It will clean out your Windows directory of all kind of orphan files which where left over from these shareware programs long since gone from your system - so you could reclaim some space in the process
You'll start with a clean registry, all "dead" keys will be gone, windows should therefore start and operate a little faster
You'll have fewer device configuration issues
It requires a higher level of experience - it could require installing hardware drivers from floppy disks, or securing newer drivers from peripheral makers
You'll have to reinstall all your applications
It requires more preparation and is tougher when installing over a network
Here are some of the pros and cons of an upgrade from another Windows version:
Setup requires less user intervention
All your Windows configuration settings will be retained
No need to reinstall your applications
It's easier when installing over a network
It clutters your hard drive with obsolete files and programs, left overs from programs you uninstalled, thus taking up more hard disk space
Specially if your Windows 95 installation wasn't a clean install either, your registry is bound to be somewhat of a mess - making it more prone to disaster
Upgrade versions usually run a little slower than clean installations
It's your call, read through these pages, and decide which way to go!
If you decide to upgrade, clean your hard disk, for more information read Cleaning up your Hard Disk (don't forget to empty your Recycle Bin!).