Let's begin by looking at the secondary sources that we have, which generally agree with each other. Polyhistor wrote that  “The Pythagorean doctrine prevails among the Gauls’ teaching that the souls of men are immortal, and that after a fixed number of years they will enter into another body.” This is echoed by Diodorus who wrote that “The teachings of Pythagoras prevails among the Gauls, that the souls of humans are immortal and that after a certain number of years they live again, with the soul passing into another body.”
  Valerius Maximus stated that “They lent sums of money to each other which are repayable in the next world, so firmly are they convinced that the souls of men are immortal.”
  Speaking of the Gauls, Pomponius Mela tells us "One of their dogmas has come to common knowlegde, namely, that souls are eternal and that there is another life....and it is for this reason too that they burn or bury with their dead things appropriate to them in life, and that in times past they even used to defer the completion of business and the payments of debts until thier arrival in another world. Indeed their were some of them who flung themselves willingly on the funeral piles of their relatives in order to share the new life with them."
  Caesar wrote that ”The cardinal teaching of the Druids is that the soul does not perish, but after death pass from one body to another. Because of this teaching that death is only a transition, they are able to encourage fearlessness in battle.”
  Lucan, in his poem Pharsalia, mocks this belief of the Druids, saying "And it is you who say that the shades of the dead seek not the silent land of Erebus and the pale halls of Pluto; rather you tell us that the same spirit has a body again elsewhere, and that death, if what you sing is true, is but the midpoint of a long life."
   Where it gets tricky, of course, is discussing where exactly the soul goes between lives. In the Irish belief it can get very complex, with many different options, often referred to as “Islands in the West”, being possible. From stories we find in the Fairy Faith, and even depending on how we choose to view stories like that of Ossain and Naimh, a person may join the fairies (the daione sidhe) for example, or their spirit may otherwise wander as Irish myth has an abundance of wandering souls to be found. Of course these examples are largely from much later periods and seeing them in relation to or connected to older beliefs is purely modern supposition. It is difficult to know what the ancient Celts may have believed about where the soul went between lives, for all that we do seem to have decent evidence that they did believe in the souls continuence. My own approach is a synthesis of the ancient evidence and the modern Celtic cultural beliefs, particularly those of the Fairy Faith minus the Christian bits, so I tend to study and incorporate both, and it usually works out that they flow together seemlessly. I offer the material I use in my own practice here for readers to keep or discard as they choose.
   Several different Irish myths discuss the topic of the immortal soul including the story of Tuan mac Cairill in the Lebor na hUidre. In this story Tuan mac Cairill tells the tale of Ireland from the beginning, which he has witnessed throughout his various lives as a man, then as a stag, a wild boar, an eagle, a salmon, and then a man again. As he says in the story "My name is Tuan son of Carell. But once I was called Tuan son of Starn, son of Sera, and my father, Starn, was the brother of Partholan." While this is obviously a story telling device it may also hint at a belief in the continuity of the soul during the rebirth process. Interesting food for thought anyway.
  In the end the evidence does seem to support a Celtic and Irish pagan belief in the immortality of the soul and of the soul's rebirth. Much may be inferred from the secondary sources and mythology but ultimately it will be up to the individual to decide how to fill in the details that are missing, such as where the soul goes between lives and for how long, and even to decide what value this belief will have for the individual. 

References:
 Freeman, War, Women, and Druids
 Matthews, The Druid’s Sourcebook. 
http://www.sacred-texts.com/neu/celt/mlcr/mlcr03.htm
http://www.druidcircle.org/library/index.php?title=Celtic_Karma