The short answer is YES, swapping valves can drastically change your amp's tone, for better for for worse! Generally speaking, the more pedals you use in front of your amp, the lower gain you want the preamp to be.
The Watford site is a good one, but it definitely presupposes you have at least some knowledge of valves.
Ian, what you are interested in doing is called tube rolling and it's VERY addictive, and can be expensive, to boot.
The first thing you need to know is that there are 3 different types of valves if you are interested in swapping.
NEW valves are either totally new designs based on new patents variations for existing valves or an attempt to improve upon an existing valve design. (For example, the EL34-B is a 'new' design, as is the 6CA7, KT77 and KT99) Different brands have different sounds. Here is where someplace like Watford Valves and New Sensor Corporation can provide you with a lot of useful information.
RE-ISSUE valves are attempts to recreate classic valve designs using modern materials and construction methods.
NOS valves are New, old stock. These are original valves, but unused. There are several sub-categories to this type of valve, including JAN (Joint Army Navy) and Siemens (my personal favourite for 12AX7s).
The next thing you need to know if you're interested in tube rolling is about valve substitution. This would involve taking your preamp or power valves and swapping them out for a different flavour of valve in an attempt to change/improve the sound.
For me, personally, I prefer using NOS preamp valves with new or re-issue power amp valves, which I feel balances out the sound quality:reliability equation quite nicely.