If it's just a side gig, then CL and word of mouth is going to be your best bet. When we look for someone to do some odd-job type things that's where we go - if I was having my whole house painted, or the outside painted that needed a lot of prep work, I would want a "real company" with insurance, referrals, website, etc.
You're going to have to do a little hustling in the beginning to get some business. Get some business cards made up that aren't the totally cheap kind - they should state what you do (i.e. outside painting? staircase painting? staining? wall AND floor tiling?) Attend landlord or REI meet-ups and start to make contacts - landlords and flippers want people they can trust. Reach out to smaller general contractors and let them know if they have small or overflow work, you can help them out... you get the idea.
Once you have a network of people, and you're EXTREMELY reliable with good quality and decent prices (don't be the cheapest, you'll just attract crappy customers), you'll have a steady flow of work. This is how DH and I had a very successful cabinet/woodworking business - this was before CL/internet.