Found this absolute gem of a utility for Fedora and Debian based linux. ManDVD allows you to add avi’s, mpegs, divx, etc to a DVD project, create a Menu and build / write the DVD. The user interface is so easy to use, probably easier than some of the windows solutions out there. It’s free and it’s available on softpedia here and also on getDeb.net
For a full walkthrough and to see how easy it is, checkout the article at dvd-guides.