It's much harder than you'd think:
http://wiki.developers.facebook.com/index.php/Photos.upload
The tricky part is how to create the MIME multi-part message in Rails, which Facebook requires. I'm also using a Ruby Facebook API gem (mini_fb) which signs my other requests, and in addition to having no idea how to set up the MIME multi-part, even if I did I'm not sure how to add in the required signature values with the gem.
Please help!