Here in the states, I’ve yet to see a store that sells Picaxe or the Arduino in stores, mostly just online. I’m not sure how you feel about Ebay, but there are alot of great deals for prototyping goodies (jumper wires/breadboards/etc) you’ll get crazy good deals.
But one thing I would do before you jump into building a robot, is start off with simple sketches first. Blinking an led… changing the blink speed, using a button, etc. There are a few PDFs on the website, I’m sure there are some better places for tutorials! (I’m more of an Arduino guy, so one of our Picaxe users will have to point that out :P)
http://www.electrokit.se/ has arduino. They are fast on delivery, and have a good webshop (in Swedish).
I just started myself, and had no trouble at all getting started with programming C.
It´s a bit more structured than basic, maybe a little more difficult to learn but more powerful. Have a look at the website http://www.arduino.cc/ , there are a lot of tutorials.
The best is that it´s all open-source, works on all platforms, easy to install and getting started with. Dont know about PICAXE, never tried.