I also often use cURL to test REST web services.
I find it more user-friendly than telnet and you can send HTTP verbs by using the -X options (e.g. curl -X DELETE $url)
Cool, I didn't know about -X. I haven't used curl since I learned about dog ("better than cat", http://jl.photodex.com/dog/), but I don't think dog offers any special HTTP options.
I just saw that wget doesn't seem to offer PUT or DELETE, but does have a lot of interesting command line parameters for people who want to get into the nitty-gritty of HTTP.