In Spanish, at least, you can see it in the definition for a (from the DRAE):
a2. (Del lat. ad)
21. prep. según. A fuero de Aragón. A lo que parece. A la moda.
Interestingly notice the last one there, a la moda. Generally with foods, you'll notice that that regional styles are always specified in the feminine. Because when you say callos a la madrileña, you're really saying callos a la moda madrileña, that is, callos preparados según la moda/forma/manera/cocina madrileña. Perhaps historically it wasn't moda, but another feminine word. It's probably mere happenstance that it wasn't "al estilo madrileño" resulting in masculine uses across the board.
Whether other ones like al vapor, al horno came out of this is a good question I don't have a quick answer to, as they could fall under a number of different definitions in the DRAE (7, 8, and 10 especially).
Another thought too is that while de is normally used to use nouns as adjectives, if you use them with things like food, de ends up meaning made out of or coming from, it'd have very different meanings:
- mejillones al vapor - steamed mussels
- mejillones de vapor - mussels made of steam
Or for a more differentiation
- callos a la madrileña - delicious tripe stew made in the Madrid style
- callos de Madrid - tripe that came from Madrid
- callos madrileños - tripe whose provenance is that of Madrid
- callos por la madrileña - tripe made by a woman from Madrid
So with de and other prepositions not working well, and según probably a bit too formal-ish sounding, ended up with just a.