I just went through all this with Joomla 2.5.x and yes, it is different. I'll try to explain how to set things up.
To get up to speed quickly, copy an existing menu. To do this in Joomla 2.5.x, you create a new menu, then copy the items from another menu to the new menu. Go to Menu Manager and click NEW to create a new menu.
In my case I copied the TOP menu, which is my main menu for the regular site. Select the menu you wish to copy from (TOP in my case) and go to the Menu Items page to show the menu items associated with that menu. Then use the "Select menu or parent for move/copy" form BELOW the list of menu items, selecting COPY and the new menu you created above as the destination menu. This is on the Menu Manager: Menu Items page.
Once you copy the menu, go back to the Menu Manager: Menus page which will now show the new menu, and to the far right you will see the link "Add a module for this menu type". Click it, which will create a module, and be sure to select the MobileJoomla position you want the module in. For now, put it on All Pages. Publish everything.
You should see your menus.
Good luck!