Saudi Gazette is an English language newspaper aimed at the expatriate community in Saudi Arabia, if memory serves me correctly.
It's owned by the Okaz Organization for Press and Publication, which is a privately owned Saudi company. They publish other newspapers and magzines too but I'll have to research
They are online at
http://www.saudigazette.com.sa/ I believe it is still subject to government censors, which can be pretty strict. Not sure what the rules are completely but in general you can't say anything negative about Islam, or the government. I'm not sure how strictly they enforce that these days.
METimes.com (Middle East Times, published out of Cairo and Cyprus) has come info on censorship there - they even publish the articles on the web that are censored from the print edition.