The answer to the original question depends on whether or not your theme is using widgets. While you say yours doesn't, I'm including the "widget" version for comparison.
1. Go to the Design menu and click Widgets. If you get a list of options in the "currently using" (right hand) column, you're using widgets. If you get an error ("your theme is not widget ready") or there aren't any widgets there, go to 2.
a. I expect the "categories" widget is already one of the ones in use. If not, drag it over to the left hand column.
b. Click the "edit" link in its title bar and click "show as dropdown".
c. Save changes
2. You might want to look for another theme that supports widgets and/or start using them and return to #1. If you've got some programming background, go to #3.
3. You'll need to edit your theme's sidebar.php.
a. You can edit it locally and then upload it the way you uploaded your theme in the first place, or you can edit on the server by going to the Design menu and selecting the menu item "Theme Editor". Then select the sidebar.php (on the right) to edit it within WordPress.
b. Look for a line with wp_list_categories. Change that line to use the Template Tag wp_dropdown_categories. You may also need to change its parameters -- see http://codex.wordpress.org/Template_Tags/wp_dropdown_categories for the options.
As for showing nested category levels, the widget has a "show hierarchy" option and using template tags gives you complete flexibility in managing nested categories.