Have you looked for local studios or agencies that will have the capacity to take you on or looked into apprenticeships? Training someone can be very rewarding but that trainee is something of a hinderance until they are up to speed, so in many cases it's not worthwhile for a single designer to take on an apprentice.
Failing that, there are LOADS of great online design courses. Just be sure you're joining a reputable one. There are also loads of tutorials on YouTube, though many are simple 'design X in Photoshop' which you don't want. Try and find content that covers the theory and thinking behind design rather than just the practical application.
There are plenty of resources to learn the nuts and bolts of using software out there.
Lynda is very good if you have an idea of what you want to learn so you can focus the time from your monthly subscription.
YouTube is also great (and FREE) but again, you need to know what you want so you can search it out.
The design theory is a bit more difficult yo learn from vid's.
If you don't want to enrol into education or (as Paul said) do an apprenticeship then I'd look into getting some general design books and start there.
Try to find what part of design interests you and then focus on that as design is a big area and getting bigger.
If you REALLY want to get into design then there is nothing you can't teach yourself really, especially with the internet.
Places like this are helpful if you want get feedback on your work and pointers from others.