The Scottish champions had far more of the play in the first half, but had to step up a gear after the break to see off the below-par Finnish outfit to make the next round
In a first half full of chances for the away side, the Scottish champions had to wait until after the break to make the breakthrough against the run of play when Charlie Mulgrew's whipped cross was chested in by the 25-year-old Welshman.
Samaras then put the game out of reach of the hosts when he converted from close range after a smart counterattack.
Mulgrew returned from suspension and captain Scott Brown recovered from a hip injury to start, with Anthony Stokes and Beram Kayal making way in just two changes by Neil Lennon.
Celtic started the stronger of the two sides, with a prolonged period of possession in the opening stages allowing Adam Matthews to knock a good cross into the penalty area for Gary Hooper, but hesitation from the striker saw the chance go begging.
The Hoops were again cursing their profligacy soon after when Mulgrew’s smart through ball found Brown in behind the HJK defence, only for the midfielder to poke his shot wide with Ville Wallen rooted in the hosts’ goal.
And minutes later Samaras got in on the act, losing his marker on the edge of the area with ease before screwing his shot well wide of the far post.
HJK were struggling to keep up with the pace of the Scottish champions, and often opted for routes down the flanks in an attempt stretch Celtic, but to no avail.
Celtic had the ball in the back of the net just before the half-hour mark when Hooper broke quickly from another clever Mulgrew move, but his reactions were too sharp as the assistant referee correctly called for offside moments later.
The home fans were getting noticeably restless as their side continued to play with seemingly little plan, as time and time again passes were misplaced or incorrect runs were made – with the Hoops more than happy to contain the Finnish side as lone striker Joel Pohjanpolo struggled to make any sort of contact with the ball in the first half.
Just one minute into the second period and HJK should be gone ahead on the night. A cross from the left squirmed its way across the box and into the path of the unmarked Sebastian Sorsa, only for Fraser Forster to impressively turn the midfielder’s shot from 18 yards round the post with his trailing leg.
The chance invigorated the hosts and winger Demba Savage lead the charge for the much-need goal by dancing around Matthews before drilling a low cross into the area, but Thomas Rogne showed good anticipating to cut out the danger.
And Rogne was needed again just before the hour mark when Savage and Joel Perovuo exchanged neat passes to find Pohjanpalo with ease between an increasingly worsening Celtic defence, only for the striker to lose his footing inside the penalty box to allow the one-time Norway international to clear.
And HJK would live to reject the missed opportunities as, almost against the run of play, Celtic scored a vital away goal with just over 20 minutes remaining.
Mulgrew, who was instrumental in all that was good about the Scottish side, stormed down the right wing and whipped an inch-perfect cross into the area to allow Ledley to simply chest the ball over the diving Wallen.
However, Lennon’s smile on the touchline soon turned to a snarl as just three minutes after taking the lead Victor Wanyama received a second yellow and his marching orders for a careless challenge on Mika Vayrynen inside the centre circle.
The Finnish side were making the one-man advantage count as they searched for the two goals needed to take the game into extra-time, without truly penetrating a much sharper Celtic defence.
And with HJK keenly looking for a way back into the game, Samaras put the result beyond doubt five minutes from time to send his side marching through to the play-off round.
Celtic will learn who their next opponents in the competition will be when the play-off draw is made on Friday.