My own experience:
I scored in the 99th percentile for the verbal section of the GRE. To prepare for the GRE, I took a live Kaplan course. I think we met two nights a week for a couple of hours. I was pleasantly surprised by my score. I think I got a 630 or something on the practice test I took the first night of class. My actual verbal score when I took the GRE was one hundred points higher. My strategy was not all that complicated: I did the homework and showed up for all the classes. I sat down with the flashcards and went through them, one by one, making two piles, words I knew and words I didn't know. I didn't worry about the words I knew. For the words I didn't know, I wrote out the definitions and then wrote sentences using those words. I enjoy writing creatively, and I made this process highly enjoyable and entertaining by writing bizarre and often perverse sentences.
During the class, you also learn a lot of tips for dealing with words you don't know on test day, and tips for dealing with the reading comprehension sections. That was where I had most of my trouble. If reading and writing etc. aren't your strong suits, it may not be possible to really improve those skills in time for the test. What you can do, however, is improve your ability to take the test. Strategy is important. (It saved my a$$ on the math section.) That, coupled with any kind of improvement in your verbal skills, should really help.
As others have already noted, read. Read good books by good authors, and keep a notebook handy for jotting down words you don't know so that you can look them up later.