That you mention Concorde places this scenario in 1976 or later, probably before 2003 when Concorde was retired from service, though your scenario may vary from this. You mention a hijacking, and while some trains can be quite luxurious (e.g. the Orient Express), they are literally railroaded and are practically impossible to hijack. This leaves only planes and ships.
The real trick with a bomb plot (other than a suicide bomber, who can also be described as an idiot) in an RPG scenario is to conceal the bomb in such a way that it can be found without it looking like it was meant to be found.
In real life, a competent organisation that has a tendency to rely on bombs (the former Provisional Irish Republican Army (PIRA) is a good example) tends to hide them very well when they want to, and they may booby-trap their bombs to a degree that gives the world's best bomb disposal experts nightmares. There certainly wouldn't be any exposed coloured wires begging to be cut that weren't a trigger for instant detonation - it would be a sealed unit. There would only be a countdown display as a psychological measure, and if I had designed the device, such a display would be totally wrong - the real time of detonation would be sooner than displayed by a considerable margin. Such bombs are typically designed such that even its maker would be hard-pressed to disarm it once it was activated.
The one saving grace of a bomb in a situation such as you describe would be that by necessity it could not include a particularly sensitive motion activated trigger - planes and ships move and vibrate too much, and that could lead to a premature detonation, so once found, as long as it is handled with minimal care and maintains more or less the correct orientation, such a bomb could be (carefully) thrown overboard. However, the bomb may be glued in place, set to go off if pulled too hard...
So, unless you want to go with the suicide bomber notion, the trick is to hide the bomb, but drop clues somehow - clues that may have gone unnoticed by the authorities, who routinely check for explosives, at least until it was too late.
A possibility that would work best on a ship could be that an NPC - who is a known bomber that the PCs may be able to associate with the enemy cabal - is arrested and shown on TV (cruise ships in the late 80s onward may have had satellite TV) being taken into custody, wearing a uniform that the PCs can recognise as being that worn by crew members of their ship, and that police found his van containing traces of explosives, but no actual bomb. It is not too great a leap of imagination for the PCs to suspect that he may have planted a bomb on board. The authorities on shore may even suspect that too, and have notified the ship's crew, who are acting as if something is wrong.
While passengers on a cruise ship move around frequently and may rarely all be together in a predictable place at a predictable time, and the PCs may have separate - and widely separated - cabins, cruise ship dinner tables are typically pre-allocated (sometimes before the voyage begins) and parties typically use the same table at the same time each night. A PC may notice when sitting down for dinner early, waiting for his fellow PCs, that there is a suspicious object stuck to the underside of the table that may not have been there yesterday evening - or just doesn't belong under a dinner table. Perhaps that vase of flowers on the PCs table is far too heavy and doesn't contain nearly as much water as it looks like it should when a PC knocks it over accidentally - and perhaps one of the flowers is a disguised antenna... This could be on a timer set for the middle of dinner, or triggered by a remote controlled by a not-so-nearby diner. Cruise ship dining rooms are big enough that a bomb that might kill everyone at a given table need not be so powerful that it would even injure someone at a distant table, and would certainly not significantly endanger the ship as a whole. The bomber could have been captured beforehand if the tables are allocated before the cruise, or otherwise he/she would need to be on board.
Another possibility is that a member of the cabal could have a crisis of conscience (or could be a pre-established informant) and decide to warn the PCs. This warning could be delivered in one of many different means, anything from a text message from a payphone or a pre-paid anonymous mobile phone, to a note on a piece of paper reverse-pickpocketed into a PC's pocket to be found at a moment convenient to the GM. This cabal member may not know the specifics, just that there is a bomb on the plane/ship that is meant to kill the PCs. Time to start searching or fleeing. A bomb anywhere on a plane is a threat, while ships would be impervious to anything but an improbably huge device. Are the PCs concerned about their fellow passengers if they are on a ship when they find out that there is a bomb on board targeting them?
A possibility that would work best on a plane is that the erstwhile hijackers were supplied by the cabal, but their bomb was real even though the hijackers were told that it was a dummy, and now it has been activated, is on a timer but it also has a heart-rate sensor and so cannot be removed from the hijacker wearing it - nor can that hijacker be killed - without it detonating. Perhaps the real bomb is on another passenger. Can the PCs bring themselves to throw the hijacker/passenger overboard alive?