The Burns Supper has a traditional format. There are plenty of resources on the internets that detail the running order (BBC website, wikipedia etc). I have chopped and welded my recommendations below.
1. A grace is said before the proceedings; the ‘The Selkirk Grace’, also known as Burns's Grace. Although the text is often printed in English (generally on a tea towel in your grandmothers kitchen), it is recited in Scots (cue silly accent).
Some hae meat and canna eat,
And some wad eat that want it,
But we hae meat and we can eat,
And sae the Lord be thankit.
2. The infamous Scottish delicacy haggis is the real star of a Burns Supper, (closely followed by whisky). The cooked haggis is often walked in, on a platter by a procession comprising the chef, a piper and the person who will address the haggis.
3. Address to the Haggis. Always a bit overdone, verses 1, 2, 3 and 8 are necessary though (when you reach the line "'an cut you up wi' ready slight'" cut open the haggis).
4. The meal
Cock-a-leekie soup.
Haggis: (it is customary to douse the haggis with a splash of whisky. Then douse yourself... internally) with its traditional companions, champit tatties and bashed neeps. Big pan of roast carrots/parsnips/onions does not go amiss here either.
Dessert: Clootie Dumpling (a pudding prepared in a linen cloth or cloot) or Typsy Laird (a Scottish sherry trifle). Much prefer the latter. Our granny made this for Christmas lunch as well, with a foaming sherry sauce... awesome.
Also: cheeseboard with bannocks (oatcakes) and tea/coffee/more water of life.
5. More Burns poetry recitals, a toast ‘to the lassies’, Auld Lang Syne.
The poetry of Burns is all well and good (though Burns only adapted the traditional The Selkirk Grace that we love), but an excuse to eat haggis is the real draw for me here. Contrary to the usual BS, haggis is no more formidable that game sausage, or black pudding. So if you like that sort of thing you will love haggis. Traditional ingredients are sheep's 'pluck' (heart, liver and lungs), minced with onion, oatmeal, suet and spices all wrapped in a sheep's stomach as casing. But please bake it, don’t boil it for gawd’s sake. Also, a good gravy is a must as it is very oaty/crumbly and needs something to stick with the mashed potatoes. The other great thing is the day after, you ball-up the leftover haggis and potato and whatever else is left and fry it in a pan. Add a fried egg and it is (whisky) breakfast of champions. The snag is that is near impossible to get real haggis in the States. Lung is not allowed in foodstuffs here, and that is a component of the ‘great chieftain’.