The Map ID can most easily be found by clicking mapbox.js on the Publish link. In the above image, my map id is highlighted in the text box.
CartoDB takes a XYZ Tile URL template, it looks generally like this,
http://{s}.someurl.com/{z}/{x}/{y}.png
the curly brackets remain in the URL, they let CartoDB (or more specifically Leaflet) know how to load the right parts of the map at a time. So the Mapbox URL template looks like this,
http://{s}.tiles.mapbox.com/v3/MAP_ID/{z}/{x}/{y}.png
the value you need to change for a new basemap is MAP_ID. My MAP_ID, given the above part of the tutorial is cartodb.map-208dddrd, so my final URL is,
http://{s}.tiles.mapbox.com/v3/cartodb.map-208dddrd/{z}/{x}/{y}.png
This can be done from any map or visualization in CartoDB. Simply click the basemap selector
and then select the 'add yours'. In the window that pops up, drop the URL you created,
click 'Add basemap' and you should be all set!