As I understand it, there are a few gems that make using Cucumber with Rails trivial. But what about situations in which Rails isn't used? Further, I'm especially interested in testing Rails and non-rails RESTful web services and heavily AJAX dependant UIs. Can you elaborate on how Cucumber can help in this regard?
Cucumber is really just the glue that binds your business-readable specifications to the code in the step definitions that run those specifications. What you put in those step definitions is up to you, and depends on the kind of app you're testing. Cucumber grew up in and around the Rails community, but it's widely used outside of Rails.
We tried to keep the book largely Rails-free. The main worked example doesn't use Rails at all. We've also got a chapter on testing REST APIs (which could be in any language) using the HttParty ruby library to automate the REST API via HTTP, which I think you'd find useful. The best Ruby library for automating web apps is Capybara, and although the chapter on Capybara does use a Rails app as the example, we clearly show how to use it for other kinds of web servers too.