I just had my request approved in a week. Surprised how quick it was considering the previous reports here.
Sent an email on October 25th with my haiku, a link to my recently updated WP.org theme, link to my support page, and description of where my statement of 100% GPL-ness was located on my website. Just got notice it was approved today, November 1st.
If you don't already have a theme approved on WP.org, getting that initial approval is by far the biggest bottleneck.
My latest theme took over 7 months to be approved. Uploaded it March 3rd, and just set live October 25th (the same day I sent my request to be included on the commercial themes page).
I don't want to turn this thread into a "how long does it take to get a WP.org theme approved" discussion but I think it is relevant to this discussion since you do need at least one to be added on the list.