Update March 2020:
It's five years later, and and eagle-eyed commenter pointed out that some documents on the matter have been declassified. Those seem to confirm my original conclusion: there were quite a few promises in oral discussions and meetings by Western foreign ministers, prime ministers and presidents. They were rarely stated precisely, but at the very least strongly implied NATO would not expand eastwards. However, there is still no evidence of a statement by NATO itself or a written promise.
Somehow, most of my answers tend to begin with "this is a complicated issue". As ChrisW suspected, there are no indications that NATO, as an organization, has made any formal promises; but there is plenty of evidence that top-level Western officials made public and private promises that NATO would not expand eastwards.
The German magazine "SPIEGEL" has run a detailed article on this topic in 2009, when Russian then-President Dmitri Medvedev raised the issue of a broken NATO promise. My answer is largely based on this; it states interviews with many of the protagonists as well as access to documents from the German Ministry of Foregn Affairs as well as other western archives as its sources.
As for formal NATO statements: Had any existed, surely there would be evidence of that in the West as well as numerous references from Russia. As it is, the Russian officials complaining about the NATO expansion tend not to make such claims. There have been claims of less formal promises made by the NATO, such as this one made by Vladimir Putin in 2007:
And what happened to the assurances our western partners made after the dissolution of the Warsaw Pact? Where are those declarations today? No one even remembers them. But I will allow myself to remind this audience what was said. I would like to quote the speech of NATO General Secretary Mr Woerner in Brussels on 17 May 1990. He said at the time that: “the fact that we are ready not to place a NATO army outside of German territory gives the Soviet Union a firm security guarantee”.
However, as Steven Pifer points out, the statement was a bit different:
This will also be true of a united Germany in NATO. The very fact that we are ready not to deploy NATO troops beyond the territory of the Federal Republic gives the Soviet Union firm security guarantees.
Here, Mr. Woerner is clearly talking about the Federal Republic as opposed to the GDR; no non-German NATO troops were to be deployed in the Eastern part of Germany according to the Treaty on the Final Settlement with Respect to Germany.
However, there is considerable variation of opinion on whether promises have been given by Western officials during the negotiations and the overall period of transition. The SPIEGEL quotes the last foreign minister of the USSR, Edward Shevardnadze, as saying no promises have been made; the same position is held by then-foreign minister of West Germany, Mr. Genscher, and the US Secretary of State, Mr. Baker. The Soviet President, Michail Gorbatchev, however, claims that of course promises had been made, and Jack Matlock, then the US ambassador in Russia, confirms that Moscow had received a "clear commitment". SPIEGEL also quotes from archival documents; Genscher is to have told Shevardnadze in February 1990: "It is clear to us then NATO will not expand eastwards".
On January 31 1990, Genscher already said in a public speech that a unified Germany would be a firm part of the Western world; however, there would be no expansion of the NATO towards the East. Genscher later explained that he was afraid of a situation similar to the 1956 Hungary uprising, when the insurgents' stated desire to join NATO provided the excuse for the Soviet Union to crack down. The US and British foreign ministers agreed with this line of diplomacy. On February 8 1990, in the Kremlin, Baker promised "no extension of NATO's jurisdiction for forces of NATO one inch to the east", should the Soviets ascent to a NATO membership for a united Germany.
However, there are also quotes showing that, at least internally, Baker and Genscher regarded this to be a policy for the very next future, not for all times. And there is no evidence of a formal or ratified decision by any NATO member state to oppose a NATO extension to the East; that is, while the foreign ministers seem to have made such promises, especially in the early stages of negotiations, no government or parliament officially endorsed them.
Finally, there is the question of why the Soviet leaders and negotiators, described in the SPIEGEL article as insisting "that everything be documented in writing, even when all that was at issue was the fate of Soviet military cemeteries in East Germany", did not request a written guarantee of NATO not expanding to the East. Gorbachev and a few others claimed the idea was plainly unthinkable at the time, so the issue did not arise. On the other hand, it might well be that the Western powers did not want to bind themselves on that issue. We just do not know and, if there is no release of new classified information in East or West, will probably not know for a while.