I'm trying to construct the Non-deterministic Push Down Automata that
accepts the following language on {a,b}:
L={a^n b^m | n<m<2n}
At first I thought this was rather trivial, however, can't seem to
find a way to do this with a single stack (only one stack can be
used.)

Are you sure this is context free?  What is the context free grammer
that describes it?

It's a regular language, so yes, it is context free (a regular
language is a subset of context-free languages from what I
understand.)

You are right that regular languages are a subset of context free
languages,  but this is most definately NOT a regular language. 
Regular languages cannot count.  a^n b^n is the canonical example of a
non-regular language, and this is a variation on that.

Hmmm, it might not be regular then...if it isn't regular, is there any
way to come up with a PDA for it?  I'm almost positive there is a
solution, I'm just note quite sure how to approach it.

As frankcorrao said the language is not regular, but
it does have a (probably nondeterministic) PDA. In this 
case it is much easier to derive a CFG, which is the 
following

s-> aTbb
T-> aTb
T-> aTbb
T-> ab

For the PDA the following strategy should work: For each a 
that you read push two a's in the stack. When you reach the 
first b pop two a's. For each following b nondeterministically 
pop either one a or two a's. If in the last b you manage to 
pop exactly one a you have an valid string.

At the same time you also have to check that your input is 
a series of a's only, followed by a series of b's only, but 
that is very easy to integrate with the previous paragraph.

I cannot see how you can produce a deterministic PDA to do 
the job, but that is not necessarily the case. I have not 
proved it, but I suspect no such DPDA exists, since m does 
not deterministically depend on n, so using the above to 
produce a NPDA is probably your best bet.

I hope this helps.

harrysnet - thanks very much!  I think that works - as stated in the
original problem, I was looking for a non-deterministic solution so
that's great.  I'm not sure how to draw your solution as state diagram
(it is much easier to state in english) - how can I combine the two
parts together in a state diagram?