How to upload new deb packages?

informally you can post them on a web site.
formally you can join the Debian community and then be the package maintainer for Debian (which is a big undertaking).
In between there are sites like nerim.net which hold repositories of stuff outside the main debian repositories.

• Xnview is not free software, so it porbably won't go into Debian unless they give permission to redistribute and someone who is a Debian developer decides to sponsor or package it
• Qemu is already in Debian: http://packages.debian.org/qemu
• avidemux is already available from Christian Marillat ftp://ftp.nerim.net/debian-marillat/dists/unstable/main/binary-i386/

For both of avidemux and qemu, you can get the Debian sources and rebuild them