When I first heard the name 'tree lobster', I had an immediate mental image of crayfish climbing trees... But I was wrong - while they're both arthropods, that's about as close as the relationship between crayfish & tree lobsters gets.
Tree lobsters turn out to be a type of stick insect - although not like any stick insect I've ever encountered! There are several species in New Guinea & New Caledonia (as well as other countries including Japan), & in 2001 another species was rediscovered on Lord Howe Island. Dryococelus australis was previously believed to be extinct, & currently has the undesirable distinction of being one of the rarest insects in the world - when rediscovered, there were only 24 individuals in one population on an isolated rocky pyramid (Buckley et al. 2008). (Since then Melbourne Zoo has begun a captive-breeding program.)
Anyway, the tree lobsters from all three regions are remarkably similar in appearance: where most stick insects have long, tubular bodies, tree lobsters are dorsoventrally flattened, with broad, solid-looking bodies. The segments on a 'lobster's' thorax are square-edged, & the males have big, heavily-spined hind legs (rather like our tree wetas). The animals congregate in groups, unlike our more solitary stick insects, and lay their eggs in the ground rather than in trees. Buckley & his team wanted to know whether this strong similarity in appearance is a reflection of recent common ancestry, or an indication of another pattern of evolution. They were also interested in the evolutionary history of D.australis - Lord Howe Island is only around 6.5 million years old, in which case the island's tree lobster could be relatively young & closely related to a species from New Guinea or New Caledonia, or else it could be much much older & with a biogeographical history all its own.
To attempt to answer these questions, the team turned to sequence data from nuclear & mitochondrial DNA. Much to their surprise, Buckley & his colleagues found that the group the tree lobsters belong to, the Eurycanthinae, is polyphyletic - the different genera have distinct, separate evolutionary origins. The Lord Howe species turned out to be unrelated to New Guinean & New Caledonian species; instead, its closest relative is found in Australia. The genetic data were supported by a comparison of the different species' genetalia (a common method for distinguishing between insect taxa that otherwise look very similar): These relatively inconspicuous but significant anatomical differences between the different tree lobster lineages mirror their separate phylogenetic placement (Buckley et al. 2008). The research team concluded that the strong physical similarities between tree lobsters from New Caledonia, New Guinea & Lord Howe Island were the result of strong convergent evolution.
Interestingly, when they calculated a date for the last common ancestor of D. australis and its Australian cousins, they got a figure of at least 22 million years ago. But Lord Howe Island emerged from the sea only 6.4-6.9mya! This suggests that the Lord Howe tree lobster originally had a much wider geographical distribution, perhaps on members of a now-submerged chain of volcanic islands to the northwest of Lord Howe Island. (Sort of an Atlantis for stick insects!)
T.R.Buckley, D. Attanayake & S.Bradler (2008) Extreme convergence in stick insect evolution: phylogenetic placement of the Lord Howe Island tree lobster. Proceedings of the Royal Society B doi:10.1098/rspd.2008.1552
The Science Learning Hub also has an excellent article on this subject.