The creature, called a Dianoga, is a pest found across the Galaxy, that originated on a planet called Vodran.
It likely arrived on the Death Star as a stowaway on a garbage ship removing trash from the Death Star. Their larva are apparently microscopic, and common enough to be considered a serious pest:
Over many millennia, dianoga migrated from Vodran by stowing away aboard garbage ships in their microscopic larval forms, and could be commonly found in trash compactors, garbage pits and sewers across the galaxy, living off any present organic matter
...
The presence of a single dianoga was often cause for alarm, since the creatures were self-fertilizing hermaphrodites, and could quickly multiply to pose a larger problem.