First of all, if you have not seen Bill and Ted's Excellent Adventure the movie which came out in 1989, then you should watch that right now. You may love it or you may hate it but it's one of those movies everyone should watch at least once. Besides, who wants to miss an early Keanu Reeves movie that also stars George Carlin? There was also a sequel titled Bill and Ted's Bogus Journey in 1991 and supposedly there is a script ready for a third movie.
As far as the game based on the first movie, it was released for the Atari Lynx (pictured above), Game Boy and NES but all were really different games. It was also released for the Commodore 64, Amiga and DOS based computers but these versions are also different from the video game versions.
The Atari Lynx version was released in 1991 and is loosely based on the movie and the Saturday morning cartoon that followed.