Do you have a rink nearby? If you do, then start there. Call them and see if they have a coach they can recommend. Tell them all about yourself - adult or not, beginner or not, etc. Then they can recommend a coach. It's a good place to start.
Another option is to go to the rink during a public or a freestyle session and see the coaches who are there. Go up to one (between lessons, of course) and ask if they would be willing to coach you, or if they can recommend someone.