This Sanskrit mantra is found at the end of the Maha prajna paramita hridaya sutra, called in English The Great Prajna Paramita Heart Sutra, or simply The Heart Sutra. Usually followed by the words 'bodhi' 'svaha', or 'enlightenment', 'may it be so'.
Literally, the mantra means 'gone, gone' (gate, gate), 'altogether gone' (or 'gone without remnant') (paragate), 'altogether gone to the other side' (or 'gone without remnant and crossed to the other side').
Though quite simple, the Heart Sutra mantra manages to pack quite a bit of Buddhist symbolism into a small package. 'Altogether gone', or 'gone without remnant' is the same terminology used to describe the state of being of one who has experienced paranirvana, the 'completion' or fulfillment of nirvana. After one has the experience of bodhi (is 'enlightened', to use the currently popular term), one exists in a state sometimes called 'nirvana with remnants', because the physical body still exists and the fruit of past karma may still manifest.
Following the death of the last body, the 'completion of nirvana' (paranirvana), one is said to have experienced 'nirvana without remnants'- one has passed beyond samsara completely, leaving no trace. Where they've gone, or if location is even a relevant question, is quite another story.
Furthermore, by 'gone to the other side', the mantra plays on the Buddhist image of the world of suffering (samsara) as a river or ocean that must be crossed using the Dhamma as a raft or boat. In some scriptures it is said of the Buddha that he has 'crossed to the other side', or the 'farther shore'. The Dhammapada, in particular, contains an image of suffering as a river, where worldly beings run up and down on one shore, unable to cross, while the wise cross using the dharma as a vehicle.
As with most mantras in Mahayana literature, various important properties are ascribed to the use of this mantra. It is said that it calms suffering and grants insight, and that it is the greatest of all mantra. Keep in mind that in the terms of the Buddhist-Hindu milieu (mantra veneration in Buddhism (sometimes called mantrayana) owes much to parallel developments in Hinduism), such a claim is not necessarily exclusive- even within one literary tradition. The Heart Sutra mantra is likely one of the better known in the Buddhist tradition- ranking behind only the nembutsu and Om mani padme hum in terms of visibility. Whether this is due to its efficacy as a charm or spell, or as a tool of enlightenment, is not easily verified.
This particular mantra has popped up in a few places in areas of popular culture, most noticeably in the works of Allen Ginsberg. Ginsberg used this mantra to frame a drawing of an exploding atom bomb in a piece published in his book Cosmopolitan Greetings. It's words are also echoed in his final poem 'Gone, gone, gone', published in Tricycle after his death in 1997.