This is on my own wishlist: How to Conquer the New York Times Crossword Puzzle: Tips, Tricks and Techniques to Master America’s Favorite Puzzle. Even if she’s really good already and might think it’s too “beginner-ish” for her, the book includes 60 puzzles ranging from easy to hard, as well as a section on creating your own puzzles, which she might enjoy.
Get hold of one of the compilations of British newspaper cryptic crosswords. It’s a totally different mindset to US crossword puzzles. The Times is the traditional one, but would be pretty brutal to start on - probably the most accessible is the Telegraph, and they do a couple of books of puzzles each year.
Mum sends me over one each year at Xmas, and it makes me feel all homesick.
How about the new Scrabble Flash game? Seems appropriate for someone into words.
Seconding the suggestion for the ‘Wordplay’ DVD. A most excellent and highly entertaining documentary. Several NYT crossword aficianados in my family and we all loved it.
Nix on this. There are books of cryptics done in the US you should do instead - British cryptics have a significant number of clues that require you to know about British rugby teams and the like. I like ones by Henry Hook. The collection from the New Yorker is a good starter; I taught my daughter to do cryptics using the puzzles that ran in the New Yorker for a while.
Here is the New Yorker book.
The NY Times has a crossword-puzzle gift section on its site, including this crossword-society subscription: The New York Times Store | Official Apparel, Books and Gifts
If she has a bunch of NYT Sunday books already, that might not work…just a thought.
It is important to know how she does crosswords. I hate mechanical pencils, and only use real pencils for mine. I also dislike computer or phone crosswords - I much prefer actual paper.
I third the suggestion for Wordplay. I saw it in the theater, and enjoyed it greatly.
Some other ideas:
There are lots of crossword puzzle dictionaries. My late mother-in-law solved with one at hand, but I never use them. If I really get desperate, which usually happens when the clue is about some obscure play or band, I use Google on my phone. That kind of thing would never be in a dictionary.
How about some books on the history of crosswords?
Crossword Puzzles: Their History and Their Cult is fairly British oriented. What’s Gnu? A History of the Crossword Puzzle is more American oriented. I just read a book by Stanley Newman with a lot of solving clues, but they are pretty elementary.
Hard to Solve Crosswords has standard clues but on interesting grids. They are kind of like the puzzles you see in Games and once in a while in the Times Sunday Magazine.
Not to throw a damper on this, but…
Some hobbyists are hard to buy hobby-related gifts for because if there’s something they want, they run out and buy it for themselves. For example, it appears this lady is more than well-stocked with puzzle books of the kind she likes. It’s possible that if she wanted a crossword dictionary, she’d have one already. While I’m sure it would be possible to find something crossword-related that she’d enjoy (a la some of the suggestions in this thread), it may be difficult if she’s the type who’s used to getting that stuff for herself.
So just a thought to keep your eyes open for non-crossword things that she might like.
If she does not know of the Jonesin’ Crossword, http://www.jonesincrosswords.com/ she should. Way more fun than NYT. As a crossword nut myself, I probably wouldn’t want my SO to get me anything crossword related because it’s subject to so many little quirks and peeves. For instance, I would never do one in pencil. In fact I only use a Pilot Q-7. Some of the suggestions above are good though, and worth looking at depending on your situation and her personal crossword kinks.
I forgot this one: Naughty Crossword Puzzles.. I picked this one up at the local thrift store, and they are naughty - and not bad as puzzles, either.
A solving aid like this answer book. This doesn’t give answers to clues; it provides answers to partially completed grids by pairs of answers, up to seven letters.
For example, if you have ?N??K, it could be
ANOUK
KNACK
KNICK
KNOCK
SNACK
SNARK
SNEAK
SNICK
SNOOK
SNUCK
VNECK
Note that this includes proper names (ANOUK) and hyphenated words (V-neck); also two-word phrases, etc.
Tell her this was recommended by a woman who was a full-time puzzle editor for 14 years, and who has been in and around the biz for 19 years. Call it 20, it’s more impressive.
twicks, who grabbed her copy from the shelf next to her computer to give you an example.
Great ideas! Thanks everyone. 
Here are some ideas.
I have a book like that, which I found more useful for solving cryptics than for traditional puzzles. (For those who don’t do cryptics, the answers have unchecked letters, and so you may end up with a situation where you are confused about an across answer even if you’ve solved all the down ones.) Cryptics have the advantage that they make you solve every clue, unlike traditional crosswords where you get answers by default if you solve enough of the clues in the other direction.
I have another neat book, for anagrams. This has the letters of a bunch of words listed in alphabetical order, so if you opera would be listed under
aeopr. I got it in England once, I have no idea if it is still available.
Voyager, who is the proud owner of a copy of Chambers, which is the standard reference dictionary for British cryptics.
A friend gave me one of these a few years ago:
A function that is also available online: http://oneacross.com/
If she likes real pencils, then I’d suggest an electronic pencil sharpener. If I’m going to use a real pencil, it has to be sharp!
FWIW, My mother loved crossword puzzles the harder the better. She really liked the ones with puns and anagrams, with cryptic clues.