I will be traveling to Cairns, Brisbane, and Sydney and was wondering what are the must try foods/dishes I should get while there.
I'll answer this question with respect to buying your food rather than cooking it yourself as that's what you'll probably be doing.
Breakfast Anywhere in Sydney you will have no trouble finding a cafe serving a "big breakfast" (bacon, eggs, fried mushrooms & tomato). If you're perparing something yourself try Australian owned/made Weet-Bix with milk or Vegemite on toast. You'll want a tiny scrape of Vegemite only; it's not jam or peanut butter.
Lunch The best lunch for travellers comes from local Fish and Chip shops, also known as Take Away Shops. We take our food away rather than "out" as in the USA. While all independantly run, they are eerily similar. Go for the Works Burger (beef pattie, beetroot, pineapple, onion, lettuce, tomato, cheese, BBQ sauce, egg, bacon) and chips.
Treats Lamingtons and ANZAC biscuits are recommended. I would scour a supermarket for snacks you do not find at home to eat on the road. In Cairns look for mangos and pineapples.
Dinner Two Australian options here are The Pub and the The Club. Either way a typical dinner would be a big t-bone steak, surf and turf (aka reef and beef), Roast of the Day or a chicken parmigiana (aka parama, schnitty). Often these are available as a deal in conjunction with a local beer. Clubs may be Returned Services League (RSL), Bowling Clubs, Surf Clubs, etc. You might have to join the club for entry which often comes with a free beer while actually costing less than a beer.
In Cairns if you are looking for something more upmarket try for the local seafood. In Sydney; how about Sydney Rock Oysters as an entree.
Late Night On the way home (actually very early in the morning, but feels like late at night) you should be picking up a kebab (aka. "Late Night Lamb Sandwich"). This consists of middle-eastern flat-bread wrapped around dubious cut of processed lamb with lettuce, tomato, cheese, hommus, tabbouleh and garlic sauce.
Drink In Sydney look for white wines from the Hunter Valley. The best reds come from South and Western Australia. Order beers that are on tap in a schooner glass (425 ml, 15 fl oz). VB and Tooheys New are common. There are various premium and boutique options. No-one drinks a beer branded "Fosters" although the same company makes lots of beers locals do drink.
In Queensland, the more common local beer is XXXX. Queenslanders seem to drink Pots (285 ml, 10 fl oz) rather than Schooners or Pints.
If you're visiting the Gold Coast, I have two suggestions for you.
And obviously, whatever you do, be sure to experience a genuine Aussie BBQ, ideally near the beach.