Too little flour and yes, it needs eggs.
http://online.wsj.com/article/SB10001424052748703555804576102420697798968.html#articleTabs%3Darticle

Probably too much liquid. Tom Colicchio goes so far as to bake the potatoes, instead of boiling, so that they are drier, and fluffy. I have not tried it myself but a friend did and loved the results. Also, use a potato ricer, if you have one, to make the texture even lighter and fluffier. The more you mash the potatoes, the gluey-er they will become.

I found the recipe for Colicchio's gnnocchis.
http://www.katyandchristine.com/2010/01/15/homage-to-tom-iii-tom-colicchios-life-altering-gnocchi/

I agree with Syronai but frankly I don't think you can salvage this mess. You might only make it worse. But also it would be useful to know which recipe you were working from. For gnocchi you do need to rice the potatoes while they are still hot----as in hot enough that you can barely hold them in your bare paws.

Without seeing your recipe, my guess is too little flour. You may also have had extra water in your potatoes when you mashed them. I usually strain the water out of my potatoes by pouring them through a mesh strainer before I dump them back into the pot to mash for gnocchi. DO NOT add eggs; that's just going to increase the goopyness.

I would try adding about 1/8 cup flour at a time, mixing it into the dough well, until you have a good consistency. If you already know that you had a lot of water in your potatoes when you mashed them, the dough may not be salvageable. Adding more flour may simply make it gluey. But since you say the dough seems very full of potatoes, there's a good chance you just need more flour. Good luck!