Yoshi is the title of a NES/Gameboy puzzle game released in 1992 (called Yoshi's Egg or Mario and Yoshi in Japan). Mario (or Luigi in 2-player mode) are at the bottom of the screen holding up four plates. Baddies from the Super Mario Brothers universe fall one at a time on to the plates. Your job is to shift the plates around so that you form stacks of the same character. Complete a stack of two and the characters vanish a la Tetris blocks.

Yoshi fits in to the whole mess in the form of a wild card. Every now and then half a Yoshi egg shell will fall instead of a character. If a top half of the egg falls and hits a baddie, it vanishes. If a bottom half lands, you can then stack as many baddies of any type on top of it as you like, and if you place an egg shell top onto the whole mess, the entire stack turns into a complete Yoshi egg. Yoshi hatches from the egg and you get major bonus points. The size of the hatched Yoshi and the number of bonus points depend on how many baddies were in the stack. Once the egg hatches, the stack clears and play continues.

There's the usual play modes: Endless and 2-player. The game was popular in Japan, but didn't see much respect or fame in the USA. Unlike other popular puzzlers it is not possible to perform combos or other such trick moves, and this may have something to do with Yoshi's lack of popularity. It's fairly easy to find in the usual used game locations and I highly recommend it as a fun and not-too-involving puzzler.

yerricde tells me that Zoocube was a heavily modified update to Yoshi by a third party, released for at least Nintendo GameCube and Game Boy Advance.