The Death Star isn't really that new. Construction of it began well before Luke and Leia's birth, as we can see it's already in this state within days of their birth:
Sure it isn't ready, but as it's so large we can assume that they will attempt to start making parts of it habitable as soon as possible, as this will mean any non-droid workers won't need to wear space suits while working on it.
People working on board the station will then require food which will in turn generate trash, so they're going to want to build a waste disposal system very quickly so they don't have to shuttle workers in and out of the station constantly as well as shuttle the trash back out.
With this in mind, all that needs to happen now is to get a Dianogra on board. As it says on their Wookieepedia article:
Dianoga originated on the planet Vodran—discovered by the Hutts prior to the formation of the Galactic Republic
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.
So really all it takes is one Vodran worker not wiping his boots before boarding the station, or a Stormtrooper who got a bit too close to a Hutt and the larva will end up on the floor and get swept down into the garbage compactor on whatever level they worked.