Thanks for the help. After banging my head against it for a while I managed to get a working (if ugly) solution.
Basically, you loop through map.layerIds, to get each "layer". In this case there are three layers: the basemap and two ArcGIS Server services that I added to my arcgis.com web map. I looped through the layers backwards (to make the top layers come first) and stopped at layer 1 (layer 0 is the basemap, which I don't want a checkbox for).
For each layer, you loop through layer.layerInfos to get the info for the sub-layers that make up each service. The label for each checkbox is myLayerInfo.name and the "checked" status is myLayerInfo.defaultVisibility. Every checkbox calls the same event and sends "this" as its argument.
Unfortunately, when I tried it with actual checkboxes (plain HTML or Dojo checkboxes) the checkboxes were almost impossible to click on an iPhone - it just wouldn't register the tap. The web map I'm making is specifically for mobile. So I tried it with Dojo ListItems in a RoundRectList, which can have a toggleable checkmark, but I couldn't find a way to store an id in the widgets (so I'd know which layer each ListItem referred to). So I ended up using a dojox/mobile/ToggleButton for each checkbox. ToggleButton doesn't have a value attribute like a checkbox does, so I had to create a concatenated string and put it in the id attribute. Not ideal but it works (so far). Maybe there's a way to have a checkbox sit inside a larger item that could capture the tap.
The event handler function gets the id value from the ToggleButton that was clicked. I've stored both the map layer (service) id and the sublayer id in the checkbox id, concatenated (this way the id is unique and has the info we need). I create an empty array. Then I loop through all the ToggleButtons on that page of the app, and for each one that is associated with the same service as the button that was clicked, I look to see if it's checked, and if so, I add its sublayer ID to the array. Once I'm done, I add a -1 to the array if it's empty, then pass the array to the service, like myLayer.setVisibleLayers(myArray). Then I refresh my legend - it didn't seem to always notice the change.
My next challenge is to group certain layers into a single checkbox (i.e. for multiple versions of a point dataset that each show only at a certain scale range), and to create radiobutton-like widgets for certain layers that should show only one from a group (like several different trail symbolizations).
I'm sure there's a better way to do all this. If anyone has seen a slick solution for a mobile map that uses an arcgis.com web map, please post a link.
The lack of examples that use an arcgis.com web map leads me to believe that most people aren't using them. Kind of like the lack of Dojo examples that use the Programmatic style (as opposed to the Declarative style) leads me to believe that most people don't use it. Live and learn, I guess.