Cast your mind back to the tenth of December. Back in England it was Human Rights Day, so it's ironic that we were spending it in China. Specifically, we were in the departure lounge of Shanghai airport waiting for our connecting flight to Sydney. By we I mean not only my friend and road dog Mitchell, but all the English-speaking passengers waiting for the next leg of the trip to Australia, for we had all grouped together, hoping that our pooled intellects could negotiate the mystical, Oriental terminal layout and the astonishingly impatient airport staff. Some might say that our adventure had already begun, but until I was safely on the other side of Sydney customs and immigration I wasn't taking anything for granted.

In case you're worried I'll tell you now that we made it. I am writing this as a free man in Australia, not surviving as a cavity-search training dummy for Shanghai's border control. The reason it's taken so long to start this blog is partly because we have been so busy all the time, and partly because Internet time is a rare and precious commodity. This will be a running theme throughout this blog; at the end of every update I'll reveal the places we've found so far that you can pick up free wi-fi, and by the end of our travels I expect to have compiled Australia's most comprehensive guide on the matter. All going well, this thing will get updated every Tuesday morning UK time, but you'll have to forgive that I've some catching up to do.

After weeks of rain Sydney brightened up on the very day we arrived. Not seven days after shovelling snow from the steps of my Bradford home I had my arm hanging out of the window of our airport pickup, and it was getting sunburnt. We dropped our stuff off at our first hostel at roughly midday, and had all afternoon to make our first sightseeing trip, to Circular Quay. This is the Sydney of the postcards, where Harbour Bridge overlooks the Opera House, and the full three hundred and sixty degrees around is genuinely the most beautiful urban scenery I've ever witnessed firsthand. Once we'd sank an extortionately priced beer by the quayside we had a short stroll through part of the vast Botanical Gardens (which is just like a regular park, except all the trees have educational little plaques nailed to them) and had time enough for a snack before heading back to shower and spend the evening getting crunk in the bar downstairs with a couple of lasses we met in Shanghai airport.

For our first week we were in pure holiday mode, and I won't bore you with every detail. We walked, we gawked, we beached on the lovely-but-frankly-overrated Bondi. We had three nights in Wakeup, our first hostel, before we travelled outwards to the borough of Parramatta to stay with an incredibly generous and hospitable couple who had been friends with my mum since long before I was born. They looked after us very well, but suburb life with an elderly couple was a massive change of pace not just from Sydney, but from our lives in England. We were getting up at seven to grab a quick breakfast and go out. We were going to bed at ten o'clock in the evening. Sober. It was great to recharge the batteries, but what we are most grateful for is our Christmas present from them: two nights in a hostel in the Blue Mountains national park. A stunning way to end our first week in Australia.

Even the train ride up to the Blue Mountains is gorgeous. You look out of the window onto thick bush and rainforest clinging to the sides of hills and canyons and it all extends out beyond the horizon in every direction. And this goes on for about twenty towns along the railway before the end of the line. You can get on a train in the Blue Mountains, go two stops up down the tracks, and there will be an entirely new and seemingly endless vista of gorges and waterfalls and cliffs and rugged mountain skyline. We stayed in the town of Katoomba, in a wonderful hostel called the Flying Fox Backpackers. Unlike Wakeup Sydney Central, which is too big and too full of strangers to really make friends with anyone outside your own room, the Flying Fox only has about forty guests at the most, and has cosy communal dining and lounge areas and - most brilliantly - has a policy of banning laptops and PDAs and phones from the communal areas between six and nine in the evening. After our first night we had no shortage of friends to go exploring with.

There were, in fact, eleven of us on the next day's trip to Wentworth Falls. Easily the most impressive of the three areas we visited, it was also the most gruelling hike (for a hike, and not a Krypton Factor challenge, is what it passes itself off as). The Blue Mountains isn't the place for you if you don't like steep steps - there are parts of the Three Sisters that are easier to ascend on all fours - but the Wentworth Pass in particular has bits with honest-to-god ladders, and one sheer rock face you have to climb down with a rope. Our Dutch action-man Arie smashed his face into the rock while demonstrating to us how to properly use the rope. I opted to just climb down the rock.

Arie first showed us his outdoors prowess on the gentle Charles Darwin Walk (so named because the man himself once did it), a flat and well-maintained path that the Wentworth Pass later branches off of. By the side of a brook we saw a family with an arrangement of strings and nets, paying close attention to the water. We asked them what they were doing and they pointed to a little monster in the stream, a lobster type creature known as a yabbie. We watched them lure it from under its rock and get it clutching onto the little chunk of lamb they had baited their line with, but they could only pull it so far towards the edge of the water before it let go and retreated again. With the rest of us distracted, Arie had just doffed his shoes and socks. He leaped down the bank into the stream, thrust his hand in the water, brought it back up holding a surprised yabbie, bang, job done. There was much adulation. Photographs were taken. "Hang on," says Arie, "I see another one." In the space of a few minutes he'd bagged three, and we had to drag him back onto the path before he single-handedly eliminated them all from the local ecosystem.

The Wentworth Falls themselves are worth the effort it takes to see them. It's not just the falls that are beautiful; at the end of every section of stairs or every narrow cliffside ledge - where you couldn't see anything for the rocks and the vegetation, even if you weren't devoting all your concentration to not falling over the side and starting a new existence living off the fat of the New South Wales wilderness, with two broken legs and arms - you are rewarded with another breathtaking view of shadows of small clouds stalking across the thick leaf canopy, lit up such untruly bright green and yellow by the Aussie sun it's like somebody's Photoshoped the very jungle, and it just goes on and on, fading eventually into the haze of the mist that turns the silhouettes of the most distant mountains blue. At the bottom of the first falls some of us derobed and went for a paddle and a bracing (read: ball-shrinkingly cold) waterfall shower. At the bottom of the next set of falls the pool was bigger and deeper and Mitch and a few others went for a swim (I was finally dry again from the first time and wasn't too fussed). Arie, the fiend, caught too more yabbies down here, and we packaged them up fairground-goldfish style in a plastic bag of water to take back and make a fresh shellfish barbecue of. By contrast, I got a land leech trying to eat my sock on the way back up and couldn't bring myself to touch it with my fingers, prising it off instead with two sticks.

If the Wenworth Pass was the main event, then the two days either side were a great warm-up and cool-down. Our first day's trip to the famous Three Sisters was a wonderful walk, if a bit crowded by tourists, and Mitch and myself had to do some off-roading to make the walk exciting. It was on a slippery plateau half a billion miles above ground (approx.), that we jumped a fence to get onto, that Mitch discovered his love of getting in waterfalls, stripping to the boxers for a photo opportunity, and getting more than he bargained for as a cable-car that minute passed overhead, full of waving and camera happy pervert sightseers. Up here I also discovered that I actually handle heights rather well, as I proved on the third day's trip to the Hanging Rock near a town called Blackheath.

The walk to the Hanging Rock is nothing but a slog down a wide dirt path for nearly two hours, notable only for the thousands of butterflies flitting about Mine and Mitch's and our German friend Tina's heads. Seriously, I've never seen so many butterflies. That bit was pretty cool. Then you don't see anything but dirt and trees until the path ends over the side of a canyon - the most impressive we'd seen in terms of sheer size. A little further down you can see the Hanging Rock itself, which is a narrow little jetty of rock bearing out over empty space, and a bit of scrambling and a couple of brave jumps over narrow but very deep chasms will get you there. For those of you who have heard of geo-caching, this was my first experience of it. There is a crack right out near the end of the rock which shelters a little gnome from the wind. In the inside of the gnome is a little plastic bag, and inside that there is a roll of paper with information about the geo-cache project and a tiny ballpoint pen with which to record your name and the date you got there. What does my clumsy butt do but drop the pen off the side? Now, not all the way off the side and into the forest, no. I could see it had fallen onto a ledge about six feet over the side of the rock. Losing the bit of green string that had originally tied up the plastic bag I could live with (sorry, whosever string that was), but I couldn't live with being the person whose fault it was that nobody else thereafter could write their name down on this unique record. I didn't want to do it, but I was honourbound. So I - yes, I am rather impressed with myself - climbed over the side and retrieved the motherf***er. Those of you read this blog know the real story. To everyone else who sees the photo of me hauling myself back up, I'm telling them I got there from the bottom.

After Blackheath, Mitch and I returned to the suburbs, for one of the best night's sleep of our lives. I cannot recommend the Blue Mountains enough to anyone who loves walking or scenery or feeling like an adventurer. Stay a night or two if you can. The Flying Fox also comes highly recommended. They provide free wi-fi to all their guests, for one thing.

Other places you can find free wi-fi are departure gates nineteen and twenty in Shanghai airport (but bear in mind you can't access Facebook in China), standing at the top of the escalators leading up to the Virgin Active gym on Pitt Street in Sydney, the bottom of the escalators on the basement level of the Westfield on Pitt Street in Sydney, platforms one and two of the Circular Quay train station, the ferry from Circular Quay to Manly, and reportedly in any McDonald's in Australia, but we haven't been able to get that to work yet. We'll keep searching, so you don't have to.

PS. When we got back to the hostel the owner Ross told informed us that yabbies are a protected species (it's not surprising given how easy prey they are) so we rehoused them in a bucket for the night to be returned to the wild the next day. No information on how they taste then, unfortunately. Probably better than breakfast on a China Eastern flight, in any case.