Tuning Forks are Key Items used in the "Trial by..." series of quests and actual items used in the "Trial Size Trial by..." series of Quests. It is easy to distinguish which NPC you should talk to to obtain your key item. The NPCs for both quests are always together; one is a Tarutaru, and the other is a member of one of the taller races, with the race and gender varying from each taller client. In the mainlands the Tarutaru are females and in the outlands the Tarutaru are males. Speaking to the Tarutaru will get you key item tuning forks for the level 65+ fights (Trial by <element>), and the taller NPC will give you the forks for the level 20 SMN solo fights (Trial Size Trial by <element>).
Normal-Sized Tuning Forks
The normal tuning forks are indeed key items, and having one allows you to fight the Prime Avatar associated with the element of the fork. To initiate the fight, merely travel to the appropriate elemental Protocrystal (e.g. the Protocrystal located in the Cloister of Tremors) and click on it to get the option to fight. If you wish to fight with others (recommended for most), every member of your party must have the key item to enter the battle.
When obtaining your key items, you must have an appropriate amount of fame in the city where the NPCs are located. You must have at least Fame 6 in Bastok and San d'Oria, Fame 5 in Kazham, Mhaura and Rabao, and Fame 4 in Norg (also known as Tenshodo Fame). You only have to obtain fame for the specific tuning fork you wish to get, but if you want them all, you must get the appropriate fame in all locations.
Trial-Sized Tuning Forks
The trial-sized tuning forks are actual items that you need inventory space to hold. There are few requirements to obtain these forks, only that you have SMN to 20 (and are SMN 20+ when speaking to the NPC) and that you have Fame 2 in the city/town you are in. When you are ready to fight, you must be SMN 20+ and trade your tuning fork to the NPC who gave it to you. He will then ask if you are ready before teleporting you to the appropriate Protocrystal. You can buff up before entering these fights, and you must fight these battles alone, just you and Carbuncle (no other avatars may be used).
If you succeed, you will be awarded with the ability to summon the avatar you defeated, and a Scroll of Instant Warp so you can return home. If you fail, you will have to find your own way home (most likely you will just homepoint when the avatar defeats you). Whether you succeed or are defeated, you will still have the tuning fork in your inventory, which you may throw out, or use to enter the fight again.