Jonathan Roudiere is making a great work creating packages for debian-based distributions, but at the moment the package situation is still in a state of flux: dependencies come and go, packages change names, and the software itself is changing rapidly.
We hope to see Jonathan's work ending up soon in the debian official repository; it should not take that long.
These packages do work (on debian lenny x86 (32-bit)), but if you want the latest and greatest version you should install from sources.
Experimental repository
The current repository is only for debian lenny on x86 (32 bit); as of 2009-06-03, the packaged version of Marionnet is also quite out of date.
You can add the repository to your apt system by appending the line
deb http://www.marionnet.org/download/debian unstable main
to your /etc/apt/sources list, and then run
sudo apt-get update
After that you can try to run
sudo apt-get install marionnet
and everything should be installed automagically.