Unlike most types of WordPress content, menus unfortunately have no "trash" concept. When they're removed, they're gone for good. We recently ran into an issue where a large set of menus were accidentally nuked...
If you don't have a recent database backup, your only option is to manually create them using historical reference points like Google Cache or Archive.org as a guide.
But in this case, a backup from the previous day was luckily available. In the database, menus reside in a variety of post, metadata, and taxonomy tables. Finding and exporting everything necessary from the backup is a little tricky, so here are some notes to help. Note this is using mysqldump to export from the backup, but you should be able to use this as a reference for raw queries, other databases, etc.
# export all posts of type nav_menu_item
mysqldump -t -u USERNAME -p PASSWORD DB_NAME wp_posts --where "post_type='nav_menu_item'" --single-transaction
# export all postmeta from the results of the previous posts query
mysqldump -t -u USERNAME -p PASSWORD DB_NAME wp_postmeta --where "post_id in (select ID from wp_posts where post_type='nav_menu_item')" --single-transaction
# export all relevant taxonomies/terms/relationships
mysqldump -t -u USERNAME -p PASSWORD DB_NAME wp_term_taxonomy --where "taxonomy='nav_menu'" --single-transaction
mysqldump -t -u USERNAME -p PASSWORD DB_NAME wp_terms --where "term_id in (select term_id from wp_term_taxonomy where taxonomy='nav_menu')" --single-transaction
mysqldump -t -u USERNAME -p PASSWORD DB_NAME wp_term_relationships --where "object_id in (select ID from wp_posts where post_type='nav_menu_item')" --single-transaction
The above will generate SQL to import in your production database and recreate the menus. But one thing it does not currently restore: assignments of menus to specific template layout positions. I think this is buried in wp_options rows that are template-specific, but I'm not positive. However, restoring the layout assignments are the easy part, so it's not a massive deal to just do it manually.