When Gandalf escaped the captivity of Saruman and was flown to Edoras by the great eagle Gwaihir, he tried to warn Theóden, King of the Rohirrim, of Saruman's treachery. He found that the lies of Saruman had already poisoned the court of the King, presumably personified by the servant of Saruman and advisor of the King, Gríma Wormtongue, already at this point. When Gandalf requested a horse, The King therefore told him to take one and be gone, not expecting Gandalf to take Shadowfax, the finest horse in the land.
Gandalf described Shadowfax as the very image of the horses from the very earliest time of the world. His speed and stamina was unsurpassed even by the horses of the Nine, and by day his coat was like silver, and by night he was an unseen shade. He would not be bear a saddle and would only be ridden by Gandalf.
When Gandalf arrived at Rivendell he sent Shadowfax back to his master, but the horse was wild and would endure no man's touch, and could not be mounted. When Gandalf helped the King see the truth, that his mind had been poisoned by the words of Gríma Wormtongue, and the lies of Saruman, the King gave Shadowfax to Gandalf as a gift to show his gratitude.
Whether or not Shadowfax went with Gandalf across the sea to Valinor is not specifically stated anywhere, but there is a great amount of hints that he did. Tolkien himself seems to argue that he did1.
Shadowfax was a Meara and the chief of his race. This further strengthens the theory of his travel to the West, as it is argued by Tolkien below. The name Shadowfax is of the extinct english word "fax" meaning hair. Tolkien seems to have been a bit indecisive when it comes to the name. During the rewriting of the story, he used both Narothal and Fairfax before deciding on the rather anglicised name Shadowfax. In the tongue of the Rohirrim the horse would have been called Sceadufax or Scadufax.
1In one of his letters (268) Tolkien addresses the question of whether or not Shadowfax travelled with Gandalf across the sea:
"I think Shadowfax certainly went with Gandalf, though this is not stated. I feel it is better not to state everything.... I should argue so: Shadowfax came of a special race being as it were an elvish equivalent of ordinary horses: his 'blood' came from 'West over Sea'. It would not be unfitting for him to 'go West'. Gandalf was not 'dying', or going by a special grace to the Western Land, before passing on 'beyond the circles of the world': he was going home, being plainly one of the 'immortals', and angelic emissary of the angelic governors (Valar) of the Earth. He would take or could take what he loved. Gandalf was last seen riding Shadowfax. He must have ridden to the Havens, and it is inconcievable that he would have ridden any beast but Shadowfax, so Shadowfax must have been there."