there. If you are using jQuery and the Web Services (hopefully with my SPServices library!), you have to do the two step process. Call GetListItems with your CAMLQuery first to get the items you need to work with and then call UpdateListItems to make the changes.
This isn't my design, by the way, it's just the way the SharePoint Lists Web Service works. When in doubt, always go to the source documentation on MSDN to see what each operation requires for parameters. I have links on all of the operations in SPServices which take you directly to the appropriate page on MSDN.
Finally, the Batch idea in UpdateListItems is a little bit misleading in its terminology. You can, in fact, "batch" requests into one UpdateListItems call, but you may or may not want to do that based on what your error handling requirements are. Again, best to check the SDK on MSDN.
I added a new function to SPServices in v0.5.8 called SPUpdateMultipleListItems to do this: http://spservices.codeplex.com/wikipage?title=%24%28%29.SPServices.SPUpdateMultipleListItems