To add to iain's w/u above, Cleopatra's Needle and its companion had originally stood outside the Temple of the Sun in Heliopolis. They were two of nine obelisks ordered to be built by Thutmose III who was the ruler in Egypt from 1504-1450 and who was responsible for many great building projects, including the great temple at Karnak. Built in Aswan and then transported 700 miles up the Nile, the two obelisks remained outside the Temple of the Sun for fourteen centuries until Augustus Caeser ordered them to be brought to his palace in Alexandria. Over the centuries the temple fell into ruin, and an earthquake caused one of the obelisks to fall and subsequently be buried under the sands of Alexandria. This is the monument that now stands on the banks of the Thames in London and is known as Cleopatra's Needle. It's companion, also known as Cleopatra's Needle, can be found in Central Park, New York.
Neither of the obelisks have anything to do with Cleopatra and were moved to Alexandria twenty years after her death. However, it is widely thought that they were dubbed Cleopatra's Needle after the place they originated as there is an area of Aswan called 'The Bath of Cleopatra', even though she is never reported to have bathed there.
The story of the obelisk's journey to England is one fraught with calamity. It was given as a gift to King George III by Mohammed Ali, a an ambassador of Egypt, in 1801 after the defeat of the French by Nelson at the Battle of the Nile. British troops based in Egypt at that time donated £7,000 towards the expense of its removal, but very little was done for many years.
Finally, almost 80 years later in 1877, Professor Erasmus Wilson a noted surgeon and Freemason ended up putting the money towards bring the obelisk home to England. Over four months, gigantic steel cylinders were built around it in order to make it float, and on the 21st September 1877, the curious barge (named the Cleopatra for obvious reasons!) was towed by the steamer Olga from the Egyptian shore*.
Unfortunately Cleopatra only made it as far as the notoriously stormy Bay of Biscay. Here the two ships were beset by a gale and Cleopatra's ballast shifted, heeling the boat over until the deck was nearly vertical. Her crew abandoned her, six men drowning in the process. For two months Cleopatra drifted in the Bay of Biscay, forsaken once again.
The craft was rescued two months later by Fillitz Morris, a Glasgow based steamer, and towed to a port in Northern Spain. On January 15th 1878, Cleopatra once again embarked, this time towed by the steamer Anglia and arrived in Gravesend five days later. From here the barge was pulled up the Thames and moored there until finally, on September 13th, the obelisk was erected upon a pedestal on the banks of the Thames. The pedestal was used as a time capsule and contains among other things: a full set of British Empire coins, a railway guide and several Bibles in different languages. These were meant to represent Victorian Britain at the time and are guarded by the two bronze sphinx that sit watching the monument day and night.
The monument, though popular, has been somewhat forgotten about over time. Having stood proudly in Egypt for centuries, the hieroglyphs on its surface telling the exploits of Pharoahs and Gods to countless generations, the carvings are being eaten away by weathering and chemical erosion at a startling rate. The once crisp inscriptions have been reduced dramatically in the past century and become less readable every year. Unless the column is protected from the rigours of London's air pollution, the carvings will become illegible, and a monument that has stood for thousands of years will be destroyed in less than two centuries.
For a picture of the strange contraption and more information about its conception and design, as well as other information about the monument and pictures of it and the sphinxes in London.
Another source is Leaves From the Log of the Mona, a vanity press book written in 1936 of one man's cruise up the Thames in his yacht. The details of the Needles journey come from there.