Mongolian food is the food of a harsh steppe climate — heavy on meat and dairy, light on vegetables, designed to keep people alive through brutal winters. This is worth knowing in advance. If you expect diverse, vegetable-rich cuisine, you will be disappointed in the countryside. In Ulaanbaatar you can eat very well; outside the capital, adapt your expectations.
Buuz are steamed dumplings filled with minced mutton or beef, often with onion and garlic. They are the national dish, eaten daily and made in industrial quantities for Tsagaan Sar (Lunar New Year). They are always good when fresh and hot from the steamer. You will eat many of them.
Khuushuur are the fried version — meat pastry deep-fried to a golden crisp. They are sold at Naadam and at roadside stalls throughout the country. Eat them hot.
Tsuivan is a stir-fried noodle dish with mutton and vegetables that shows up at every canteen in Mongolia. Better than it sounds. Portions are large.
Khorkhog is the countryside celebration dish — mutton cooked with hot stones inside a sealed pot or milk can. It is rich, fatty, and ceremonially passed around with the hot stones, which are supposed to be good for your health if you hold them.
Boodog is the same principle applied to a whole deboned goat or marmot: the meat is cooked from inside using hot stones. It looks alarming and tastes wonderful. You are unlikely to encounter it without a deliberate effort — it is a feast dish.
Airag (fermented mare's milk) is the drink of the steppe — slightly fizzy, mildly alcoholic, and completely unlike anything you've tasted. It is offered everywhere in summer when the mares are producing milk. The polite move is to accept a bowl and drink it.
Salty milk tea (suutei tsai) is served at every ger, every hour. It is made with black tea, water, milk, and salt. Many visitors find it odd at first and develop an attachment by the end of the trip.
In Ulaanbaatar, Korean, Chinese, Indian, and Japanese restaurants are all easy to find, along with decent coffee shops and some genuinely good international restaurants. The restaurant scene in the capital has improved dramatically in the last decade.
One honest note: the dairy products made by nomadic families — dried curds, clotted cream, fried dough — can be wonderful when fresh and made well. They can also be sour, hard, and challenging. Roll with it.