the advice about having a play with different cameras is very good. being able to use a camera comfortably and without always having to look at the dials is a great aid to getting better pix. you are concentrating on the picture, rather than the means of capturing it so to speak.
personally, i have been a Nikon/Leica user for my whole photographic career. i have always found Nikons to be great bits of kit. i have never been too keen on Canon's, but thats just a personal preference, many colleagues use them and love them
look for megapixels in the CCD (at least 4), optical zoom (don't use digi zoom, ever) and lens quality.
lens quality is of extreme importance, i would only buy a digi camera with one of the following makes of lens: Nikon, Leitz (Leica), Schneider, Rodenstock or Carl Zeiss. there is no point having a 15 megapixel camera with the optical equivalent of a coke bottle jammed on the front.
also, budget for a BFO (thats Big F$@& Off) memory card, whatever comes as standard is too small.