With Windows XP you should have at least 512mgs of RAM, but it will run with 256.
Be aware of the Video RAM. Shared will say something like 128 mgs video ram, with 64 megs shared. That means it uses system ram to augment the 64 megs of ram actually on the card.
You will get what you pay for. Go cheap and you'll feel it in time. I'd suggest a moderate price range that's not the tip top of the line in terms of technology, but not at the bottom either.
I like Athlon better then Pentium, but pentium better then Celeron.
If you have a CDRW drive (or a DVDRW, which would be even better) the 40 gigs will be enough space for programs, but the more space the better is the rule.