Amount of water on Earth is estimated at 1.386 billion km³ - let's get rid of the decimals and take it at 1 billion km³. Means 109+9=18kg of water.
Let's take the average initial temperature at -200C, to account for some heating done by the planet's core and energy gained by various tidal sloshing happening during planet's braking and getting into the parking spot at destination.
Now, the specific heat capacity of water and ice are, respectively 4.187 kJ/kgK and 2.108 kJ/kgK with the heat of fusion for ice (which, in reverse, is how much heat you need to make a kg of ice to melt) is 333kJ/kg - yeap, no mistake there, those weak hydrogen bond forces that keep the water as a crystal surely pack a punch.
So, to melt that ice to 20C, you need:
- heat the ice to 0C - takes 200*2.1*1018kJ = 4.2e+20kJ
- melt the ice to water at 0C - takes 333*1018kJ = 3.3e+20kJ
- heat the water to 20C - takes a puny 20*4.187*1018 kJ or about 8.3e+18 kJ. We're gonna neglect this.
Grand total, with a single decimal 7.5e+20 kJ.
Total solar irradiance upon Earth - 1.365 kilowatts/sqm. Allowing some loss for reflection/scattering in the atmosphere, we get 1kW/sqm.
At a planet radius of 6300km (a wee smaller than the Earth), we get the planet's cross-section on the solar flux of 1.25e8 sqkm = 1.25e14sqm.
Let's assume the planet is painted as black as the space where it came from (boy, surely lotsa smoke there from those burning stars) and happily absorbs all the solar radiation (minus atmospheric losses).
With the above we get 1.25e14 kJ every second. To get to the total energy required to melt that cold ice and make luke warm water, is gonna take 7.5e20/1.25e14 = 6000000 seconds.
Which is to say, the planet cannot thaw in less than 70 Earth-days.
Now, the things are a bit more complicated:
- the atmosphere won't kick in until the gases evaporate. Which may be a blessing and a curse, 'cause of course the planet is going to receive more energy without an atmosphere (10%-20% more), but is going to lose part of the energy by radiation at night
- there's no way all that ice is going to absorb all the energy, 'cause albedo
- there will be some ice that won't melt, around the planet's poles
- there's not only the water, but at least some 20 or so meters of soil would need to thaw as well
- once the equatorial areas are ice free, the energy is going to be absorbed faster and the atmosphere will distribute the heat towards the poles, accelerating the process...
- ... but with the water getting into the atmosphere, the clouds are gonna reflect more.
Let's say the thawing of the top soil amount for another 25% and, as we ignored over 0C temperature anyway, let's say the ice albedo allows only 5% of the energy to contribute to heating.
In this case we have 70d*1.25/0.05 = 1750 Earth-days = 5 Earth-years to be considered as the new "lower limit, can't heat it faster".
One on top of the other, feeling of guts, I'd say one should expect a no-longer-deep-space-frigid planet no sooner than somewhere in the 100-1000 Earth years as order of magnitude.