The 2e Priest's Spell Compendium (a set of 3 books with all the divine spells from 1e and 2e in it) had a table with suggested rules for obtaining/researching new forks. While it's ambiguous in 3e, I treat the foci as it was in 2e, a tuning fork that works on a very specific frequency, and the frequency is unique to a plane.
Personally, I'd say that any organized faith with Clerics (i.e. that grants Plane Shift) would normally be able to provide (at cost) tuning forks for the Material Plane/World that the Church is on, and a fork for the deities home plane (if the deity didn't mind the occasional traveller). If the deity objected to visitors, or he was a deity of travel, they might provide a fork for any reasonable plane.
Now, the way it was written in the 2e compendium was a little table based on destination. For 3e, I'd make it a Spellcraft check requiring a full sized research library (the same basic rules as for Spell Research). The forks cost anywhere from 100 gp to 400 gp depending on how rare the destination is (demiplanes being most expensive, inner planes and Material Worlds being cheap, and Outer Planes being intermediate. While it's not given, I'd also make transitive plane forks relatively cheap too). The research usually takes anywhere from 1 week to 1 year (again, with more common destinations like transitive planes and the material world being far easier, while demiplanes being pretty much all the stuff beyond a few months) and costs anywhere from 500 gp to around 15,000 gp (get an idea of what was cheaper and more expensive by now?)
You might also treat it that a deity of travel or knowledge could even have all the answers written down and available to priests, just go to the nearest major temple, verify your identity with the faithful to get access to church secrets, and be shown the specifications for the foci you want, and it's a simple matter of paying for the materials or obtaining one from the churches supplies, and being just tuning forks they are relatively cheap and go for pocket change to a ~9th+ level PC (a few GP).
You might be able to sidetrack the whole issue with a Commune spell or other divination, if the deity is inclined to let his priests just go planewalking, spending the XP for a commune to get a specific "note" or other identifier for a specific Plane Shift foci, but these are both the easy ways if you want to make the forks relatively easy to obtain.