It mostly works.
For Debian it works, it's very rare that a program you want is not aviable thru their official mirrors. However some 3rd party repositories exist for some programs (mplayer is a good example of this). It's best to keep 3rd party stuff down to the minimum amount. Debian's packages and maintainers are very high quality and disicplined.
They tend to be a version or 2 behind for big programs. Like Gnome and KDE will be a couple months behind other distros. XFree86 is not going to be upgrade for a long time, yet.
Fedora is pretty good. It's more up to date, but the package selection from official servers is much more limited. I have come to depend on 3rd party repositories which can cause problems if you mix and match to much.
Good 3rd party Fedora repositories are Dag's RPMs, Atrpms, and FreshRPMS. They do a OK job of making sure that they keep comptable with everybody else.
The only trouble I have is that when I install Fedora's official apt-get package it gets over written with 3rd party repository's versions, and then I have to edit the stuff all over again.
The advantage of Fedora is that it's more up to date and easier for most people to adjust to then Debian. Disadvantage is that it's more likely to mess up, which takes some effort to fix, and it's slightly less stable then Debian.
It may be better to use Yum for Fedora. It does the same thing as Apt-get and is installed by default, unlike apt-get which you have to download and install seperately. I think yum is the prefered method. Guys I know that are Redhat fans use Yum.
Fedora package related sites:
http://www.fedora.us/wiki/FedoraHOWTO
http://www.fedora.us/wiki/RepositoryMixingProblems
http://dag.wieers.com/home-made/apt/
Debian sites:
http://newbiedoc.sourceforge.net/
http://www.debianhelp.org/
http://www.debian.org/doc/
Note with Debian you have 3 flavors.
Stable, Testing and Unstable.
Testing is like Debian's Beta OS. Eventually it will be the next Debian Stable OS. Shortly Debian is going to release a new OS, so Testing is at a pretty stable state right now.
Unstable is were all new stuff is introduced. It's unstable because it's changing constantly. Packages are tested here until they are acceptable for acceptance in Testing.
Stable is unchanging. Only bug fixes, never any new features. It's pretty dated right now, and I'd recommend install Testing or Unstable over Stable, unless you have bunches of computers to maintain or want to run a server.