Keep in mind that REST's 2nd most important feature is its catchy acronym, (Its most important feature being its beautiful simplicity).

You may be able to proceed with LWP::Simple calls (assuming stateless operations). LWP::Simple::Post may be needed *if* you know the right parameters, but I've had marginal luck getting the latter to function, so YMMV.

If you need to PUT or DELETE, you'll have to dig into LWP::UserAgent and HTTP::Request.

And once you've gotten your response to any of the above, you'll need a suitably capable XML processor...if you're lucky, just XML::Simple (if you're really lucky, just some crafty regexen).

FWIW: DBD::Amazon is REST based and, by far, that was the easiest part of the package development. I'm always amazed at the BFD that is made over SOAP interfaces. I guess the Java/Web Services crowd can't abide a solution that's less then a KLOC.

Go REST, young man, go REST!