I'm not sure I believe the rather interesting theorythe rather interesting theory that it's a sanitised version of "Christ on a cross" (cf the overtly blasphemous "Jesus Christ on a bike!"), but I've always been partial to...
Apparently the general consensus is it's primarily/originally an Australian term, but I quite liked a Scottish rock band of that name in my early teens, so it's always seemed perfectly "British" to me.
The more common (and more definitely, British) "Stone me!" doesn't strike me as blasphemous.
