The earliest evidence of forks I've come across is in 12th Century italy (well ok, Venice, since italy didn't exist yet). Before this time eating utensils were a spoon and a knife.
However, forks were rather slow to take off. By the 14th Century france had adopted the fork, by england held off adopting these inventions of hte hated foreigners until after the time of henry VIII.
In period times all forks were two pronged forks.
Since it's rather difficult (and probably non-period) to eat without using you fingers with only a knife and a spoon, a serviette (or at a pinch a tea towel) is an extremely useful item, as it prevents getting nasty hard to remove grease stains on your garb from the roast chicken and making the hospitaller angry if you borrowed the garb.