Just use the --python (or short -p) option when creating your virtualenv instance to specify the Python executable you want to use, e.g.:

virtualenv --python=/usr/bin/python2.6 <path/to/new/virtualenv/>

N.B. For Python 3.3 or later, refer to The Aelfinn's answer below.