More details:
My girlfriend knew this was happening - we met in February, so been dating just around a year, she didn't know when or how I'd ask, but she knew. I did the ring work alone aside from getting her sized one day. I did formally ask her dad as well.
I chose my house for the location as a) it was where we met, and b) my backyard is awesome
But basically I told her we were going to the zoo, and she came over. I had a note on the front door to "follow the roses" when she opened the door I had rose petals leading her to the back yard ($40).
I cleaned my back yard really nicely, so she came out and I had a scrapbook ($110 for custom made scrapbook a replica of Our Adventure Book from the movie Up + around $20 for photo printing and scrapbook stuff) on my garden chair with more roses.
I watched her through the window and when I knew she was near the end, I went out.
I learnt one of her favourite songs (You & Me by Lifehouse) on guitar (guitar cost me $80 from GumTree, lessons were self-taught using tabs). After playing for her, I poured my heart out and proposed.
She said yes.
My tips: really understand her - don't go out and do a big public proposal if you know that she would get embarrassed and conscious. Keep it simple. Think about your relationship, the key parts to it and what makes you and her special.