In Dubai, you won't have much of a problem, although as others have already pointed out, bring your own tobacco - you can find a few blends in country, but most of the tobacconists are very cigar-centric, offering only OTC blends. I seem to recall the duty-free in the airport had W.O Larsen, Peterson and a few of the STG blends available. I haven't travelled to Oman, so I'm unsure how you will find it there.
I would also suggest looking for a mediwakh and some dhokla while in the Emirates. The mediwakh is a very small pipe (similar to a kiseru in size), while the dhokla is a granulated tobacco/herb mix. It's awesomely potent stuff if you're a fan of the vitamin N, and is pretty damned tasty stuff.
To expand a little on what cleidophoros has said, tobacco smoking has been taking place in the Middle East for as long as it has in the European West - however, the Ottoman Empire also produced some of the most vehement of anti-smokers in recorded history. In 1633, the Sultan Murat the 4th implemented a standard penalty for people caught smoking - first, they would have their noses pierced, and the pipe stem inserted for a parade through town. Once they had been shamed, they would be sentenced to death through drawing and quartering, or, if the Sultan was having 'a good day', they would simply have their hands and feet crushed. Fortunately, nicotine is a hell of a drug, and after murdering (by some accounts) upwards of 20,000 smokers, the law was rescinded in 1647.