Valentine's Day 2006, I booked us a surprise trip to Hawaii (Waikiki Beach on Honolulu). I cleared being gone a few days from school with her professors (we were in college)--one of them had a test scheduled, but he let her take it another time. I also got her a few days off work. She had no idea I did any of this. A few days before I said I had an early present for her, and she'd get it when she got home from work (around midnight, she was working the closing shift). I had a card that said "The most important thing about Valentine's Day?" and on the inside "Location, Location, Location." and showed a bed. I drew palm trees and a beach around it, and put an itinerary in, and when she opened it, I said "pack your bags, we leave in a few hours." She was quite surprised/excited (and I told her it was all cleared w/ her professors/work).
We went and had a great trip. On Valentine's day, after being there for a few days, we went on a sunset dinner cruise, and before dinner when we were on the top deck looking at the sunset and ocean and island I got down on one knee and proposed. She grabbed the ring out of my hand and shoved it on her finger. I said "I take it that's a yes?" It was. We had a nice dinner and another nice day or two in Hawaii, then flew back home.
Her family had all guessed I'd be proposing (Valentine's Day in Hawaii?), but she had no idea, because I had been throwing her off with wanting to wait a bit longer, so she was very surprised (first at the trip, then at the proposal).
Been almost a decade now, and it was still the best decision I've ever made, and I think it always will be.
(The trip was very Mustachian, got a great deal on it, and on the ring. ;) )