I have that one. It works by showing the positions of sun and moon. If neither are above the horizon, it can't give direction. It's better than nothing, and costs nothing and weighs nothing so I figure I might as well have it.

Another Java astronomy program is http://www.piecafe.co.uk/solun/jsolun.htm. Kinda cool if you like to look at your mobile phone and say, "My god, it's full of stars."

I have one of those, too. It's physically huge, and I think they all are. If that bothers you you are probably out of luck.

I know what you mean. I sometimes find that taking stuff off the keychain, but still in my pocket, it is less obstructive.

You can make a compass by magnetising a sliver of metal and suspending it from thread or floating it on water. Traditionally a needle is used, but you probably don't want something pointy in your pockets. Anything reasonably long and thin and made of the right kind of metal will do. (Of course, a needle is a valuable part of a sewing kit in its own right, so you may already have one.) A home-made compass like this can be hard to use in difficult conditions (eg windy) and isn't much good for taking bearings or following one - but frankly we've not set the bar very high with the phone and watch tools.

It is of course worth knowing how to tell north from the pole star, from the sun, and from the moon. Eg

http://www.edibleplants.com/month/moonorth.htm

http://www.wikihow.com/Find-True-North-Without-a-Compass