Passing query vars in the permalink

I’m sure this is really simple for the right person. I’ve read extensively from the codex and other sites but haven’t figured it out yet.

I want to append query vars onto urls using the permalinks. My plugins only work currently by using the ?variable=x method and I would really like to have them as

http://blogaddress.com/category/examplecat/variable/x/

or even better

http://blogaddress.com/category/examplecat/x/
(where ‘x’ is in a predefined pattern to be recognized)

Thanks for the assistance toward better plugins for the community.
Dyasonhat!