I would personally aim for the Canon EOS 500D, as it's a better overall camera if slightly less accomodating for the beginner. The video mode is better as well. The D5000 has a guide mode and takes some cracking images, but falls down in the moving images department. If you aren't bothered about video and have little photographic experience I'd probably steer you more towards the D5000, but you can't really go wrong with either.
Wave has made a good point - if you get serious about your photography than you may end up spending more on the lenses than the original body. Think about it carefully. Both Canon and Nikon make lovely cameras but once you buy a Canon you will not be able to take advantage of the Nikkors (and vice versa). I agonised for a long time, 5 or 6 years ago, and went for Nikon and have no regrets. I am sure there are many people who would say them same about Canon.