This expression, which I have heard more times than I care to remember in all the states of Australia and in the UK, is actually rendered in full as:

Up Shit Creek, without a paddle, in a barbed wire canoe.

The expression is a typically Australian one, relying on multiple metaphors to obscure the meaning as much as possible. The three metaphors are as follows:

So there you have it. The only thing that remains it to put this phrase into a few sentences. Here are a couple:
  • "Mate, me missus has caught me red-handed with my bit on the side! I'm up Shit Creek in a barbed wire canoe, without a bloody paddle!"
  • "I hear your chariot broke down outside Newcs?"
    "Yeah, we were up Shit Creek without a paddle in a barbed wire canoe until the towies arrived."

The Australian focus here is easily explained: researching this phrase has provided some evidence that it was coined in World War II by Australian Diggers. It has certainly been in common use in Austalia since the 1950s, and was one of the many colloquialisms uttered by Australia's unofficial ambassador during the 1960s, Barry Mackenzie. Whatever its origins, the phrase and variations are now in common use throughout the English speaking world.