Download the QC (QuakeC, a properietry language similar to C but for Quake mods) source code from ftp.idsoftware.com, and grab a copy of FrikQCC (a QC compiler that by far is better than id softwares one, search google for url).
Once you have those, you can begin coding the modification. Once you've made your changes to the code (the QC files), compile it to produce your "progs.dat" file. Create a directory under your Quake folder (with any name, tho make it something like an abbreviation of your mods name) and place the newly made progs.dat file in it.
Now start Quake with the command line parameters "-game (modfolder)", where (modfolder) is the name of the directory in which you placed the new progs.dat file. Quake will load up and use the new game code instead of the original game code.
There are many 3d modelling tools around that you can use to design models, and many map editing tools. Check out www.telefragged.com/openquake for a listing of many sites Quake related. There are many engine modifications as well as tutorial sites and general modding sites.