How can I specify a dependency between 2 versions of a package?

The operators for version dependencies are:

>>  Greater than, but not equal to
>=  Greater than or equal to
=
<=
<<

(note < and >, meaning <= and >= also work, but they're depricated)

So in order to declare your example, you'd add two dependencies:

Depends: python (>= 2.5), python (<< 2.7)

For a full description of dependency declarations, see the Debian Policy Manual, Chapter 7. If you want to take a look at some uses, see this random example.

You can use two clauses to specify the constraints. The first states a dependency on python 2.5 or greater, and the second states a dependency on python earlier than 2.7.

Depends: python (>= 2.5), python (<< 2.7)