So far the only way to increase it for me is a monocle that I found somewhere along the way that gives +1 to the quality. I just encountered a storylet that has an action that checks this quality for success rate. How do I increase the Respectable quality further?
There is one (1) way to gain Respectable inherently: follow the story of Millicent Clathermont (the Lady in Lilac) during the Feast of the Exceptional Rose in February 2014 (unavailable now, but hopefully repeating again in future years), prepare to get a tattoo, and then opt out of it — tattoos are for the gutter folk, and you are more Respectable than that.
Otherwise, the only way to raise your Respectable is to gain equipment that grants a bonus to Respectable. The earliest place to raise your Respectable is with a Connected Pet, acquired through the quality A Clandestine Rendezvous at Watchmaker's Hill, which you can pick up in turn from a few gold-bordered opportunity cards drawn while you are in Veilgarden, Watchmaker's Hill, Spite, and Ladybones (the starting areas). If you already have one, then when its card comes up, get rid of it and grab a different one — the Church, Dockers, Revolutionaries, and Society Connected Pets will grant +1 Respectable.
The Bazaar tab, with its shops, has a few of these, mostly in Dauncy's and Fadgett & Daughters, and the cheapest way to get +1 Respectable costs 28.80 Echoes. In Nassos Zoologicals, you can pick up the Midnight Matriarch for a mere (!) 400 Echoes.
The biggest ways to raise your Respectable quality happen once you become a Person of Some Importance, where you can finally get inventory items to fill your Affiliation, Transportation, Ship, and Club slots in the expanded inventory. Between those four inventory slots, you can pick up +12 Respectable, using an Association with God's Editors (+4), a Respectable Landau (+2), a Luxury Yacht (+2), and joining the Parthanaeum (+4). You do not need quite that much respectability, but you can get it.
(To become a Person of Some Importance, raise your main stats to 100 (including item bonuses), and wait for an opportunity card with the Ambitious Barrister. All four of these items will present themselves to you one way or another once you become a Person of Some Importance; it's fairly hard to miss. Just note that you can only have one Ship and one Club, but you can pick up as many Transportation and Affiliation items as you like.)
TL;DR: Respectable (and Dreaded, and Bizarre) is expensive and difficult to raise, and you will not be able to do it much at all until all of your stats hit 100 and you can become a Person of Some Importance.
I suspect you've just picked up a Connected Pet, as that's the first time I can recall having a Respectable challenge. It's going to take several tries to succeed at the Respectable challenge on your pet.
One of the Fallen London Wikis has a guide to being Bizarre, Dreaded, and Respectable, if you need incredible detail.
I'd prefer to attach this as a comment to Paul Marshall's post, but for some reason you need to have 50 reputation to do that. I have 47.
Millicent's story was repeatable this year, and it probably will be in years to come as well. Anyone who did it last year was able to obtain a second tattoo (my character now has two eyes on their back), meaning that this is an extremely reliable, if somewhat slow, source of BDR.
This is a bit of a digression, but of the three notable qualities, Dreaded is probably the most valuable; there are more storylets that require a Dreadful reputation than there are for the other two. Bizarre is the hardest to raise, and therefore is a fandom favourite.