What is the easiest and cheapest way to rectify this problem? I am not too tech savvy so some crazy mumbo jumbo is not going to help me and will just make me angry. :P  Also, it would be preferabble if the solution does not involve voiding warranty.

Delete stuff. Or use your secret alternate HD that is 5 times bigger than the one you normmaly use.

Get a bigger harddrive. Swapping the PS3 one doesn't void warrantly. It's also not a techie job to replace.

Alternatively just delete some stuff - PSN games you no longer play - you can redownload them anyway, game installs of games you no longer play - those are under Game Data or similar in the Game menu, video files you put on the ps3 (though maybe not ones you bought and downloaded, since some of those can't be redownloaded, I think).

Are you sure switching hard drives does not void warranty? What about external hard drives? Do they work with the ps3? Can you play things directly from the external hard drive? (for example, if I bought Castle crashers, put it on the external drive, could I play it?

100% sure you are allowed to swap the harddrive. I think you even get instructions on how to do it with the ps3 booklet.

You can use external USB drives for video/photos/music, but not play games off them, I think.

This post is 100% correct. The instructions to do so are in the book and it doesn't void the warranty. The last sentence is also true. I have an External hooked up to my PS3 all the time.

So I can not play games directly off an external hard drive? :(    Oh, well, I probably will upgrade my hard drive soon so thanks. Now I just have to find that manual that you spoke of....

You can just google or youtube it, it's pretty simple.

Mind you, you still have to transfer your stuff to the new hdd, so you'll either need a big enough external drive, or delete everything you can easily re-download/reinstall and backup to a usb stick. Then restore from backup once you have the new drive in (all this stuff is in the system menu).

I think even copy-protected saves can be restored as long as it's the same PS3 console, but I haven't done that so somebody correct me, if that doesn't work.

I have a 80gb HDD for my PS3 and what i do to keep space is delete game datas that i've been required to install when i played them.  If there are games you use to play that required lots of space and no longer play them then you can delete them.  You're not deleting your save data file so if you ever did decide to replay a game where you left off you'll just simply have to reinstall the game data again thats all.

It comes with your PS3. Also, I believe that SONY keeps an online version of the manual at playstation.com. And I don't really want to get up and check but I think there's a link to it on the PS3 the same section as the web browser