We Love Katamari

The King and Queen of all Cosmos are in the 500 m level(the elephant and bird). Once you get around 3,000m you can pick up the King. Once you do that, play the level again and, at about the same size, you can pick up the Queen. Once you get big enough they aren't to hard to find. They're huge.
Good luck!

The King and Queen are located in the Elephant and the Bird level, where you have to get the katamari over 500 meters in diameter. Get it over 500 meters as quick as possible and keep rolling over objects after you reach your goal. Eventually, if you get it big enough (roll over land to get it larger faster), you will see the King of All Cosmos and the Queen running around. Once you push into the King and/or Queen, they will be yours for the taking. Roll them up, and you'll reach 100% in your collection. Get some practice on the other stages if you're having trouble.