First, the patent system doesn't care about software licenses. Conversely, copyright doesn't care about patent licenses (it's automatic anyway). The only place where patents and copyright might interact is in licenses, which are contracts which might grant someone additional rights that they would not have given the restrictions imposed by patent and copyright laws (such as the right to perform a patented method or to distribute a piece of software).
Second, you can't patent a piece of software. Generally speaking, what is patented is not a device as such, but the way the device works. For example (prior art aside), you don't patent a Ford Model T, you patent a vehicle on four wheels, or a piston engine, etc. When it comes to software, what is really patented is the algorithm. See What constitutes an original patentable idea in software? for a more in-depth treatment.
If you write a program that uses a novel algorithm, you may patent the algorithm. You must file the patent before you distribute the program, under any license (in the US, you have a 1-year grace period in some circumstances). The GPLv3 is a contract where the copyright holder declares that he will not enforce any patent that the software may relate to (I'm simplifying somewhat but that's the gist of it). Other licenses, including older versions of the GNU GPL, do not preclude having patents.
Note that it is possible to unknowingly write software that violates a patent, for example if the author independently rediscovered an algorithm. Thus even the GPLv3 does not guarantee that a piece of software is unencumbered by a patent, only that it is unencumbered by patents assigned to the grantor of the license.