Working with PIC chips in Linux is both a daunting and a surprisingly easy task at the same time.
First you need to get yourself a PIC programmer. The one I got was a clone of the PicKit2 off ebay for only a few pounds. There are many others around. The PicKit3 is probably a better option that the PicKit2, but I have had good results with mine so far.
Secondly there is the software. For the actual programming of the PIC, you will need software suitable for the programmer you get. For my PicKit2 I use the Linux command-line utility
pk2cmd downloadable from Microchip. At first, when I started using it, I was very very lost about what the command line options were - the documentation is rather poor. But, after some digging I worked out the following command line that I always use:
$ sudo pk2cmd -p -m -r -f file.hex
That auto-detects the chip you are using (-p), programs all the memory (-m), resets the PIC after programming so it runs (-r) and uses the file /path/to/hex/file (-f ...)
Another useful one is:
$ sudo pk2cmd -p -i
Which tells you about what PIC it has detected.
Now, I ran up against a problem with pk2cmd recently - it doesn't support the very newest PIC chips (in particular the PIC18F46K22 I was trying to use). However, there is another version somewhere on the Internet (I can't remember where right now) which has been modified to support the very latest versions of chips. You may or may not need that depending on which PIC you go for.
Then there is the programming of the firmware itself. Microchip have very thoughtfully ported their MPLAB-X IDE to Linux, so you can get all the software you need for the programming here. It's still in beta at the moment, so expect a few bugs, but you can get the IDE, and all the C implementations you like there. The on-line documentation inside the IDE is pretty good, but you will need the data sheet for your chosen PIC at hand.
While there are other IDEs available, this is the one I have had best results with (i.e., it's the only one I have actually had working under Ubuntu).
PS. I have community wiki'd this answer so people can build on it.