[1] James Voelkel suggests that the characters were named after Frederik Rosenkrantz and Knud Gyldenstierne, cousins of Tycho Brahe who had visited England in 1592.
When James VI was at Elsinore (Kronborg), a servant of Axel Gyldenstierne, captain of Akershus, was rewarded for bringing letters to the Scottish king.
The names were common in the court of Frederick II and Christian IV, and also at the University of Wittenberg, an institution where Hamlet is mentioned as having studied (he refers to them as "my two schoolfellows").
[1] The two courtiers first appear in Act II, Scene 2, where they attempt to place themselves in the confidence of Prince Hamlet, their childhood friend.
The smooth and courtly language they employ immediately establishes them as sycophants[1] really serving as spies for the corrupt King Claudius, Hamlet's uncle, who usurped the throne and constantly attempts to check his nephew.
When their ship is attacked by pirates, Hamlet returns to Denmark, leaving Rosencrantz and Guildenstern to die; he comments in Act V, Scene 2 that "They are not near my conscience; their defeat / Does by their own insinuation grow."
[1] Shakespeare expects the audience to appreciate the poetic justice of their deaths:[1] while they are very likely ignorant of the deadly contents of the letter they carry to England and are, to that extent, innocent victims of Hamlet's retaliation, they are seen as having received their just deserts for their participation in Claudius's intrigues.
He does this by making Rosencrantz and Guildenstern unsure of who is who, as well as having the other players (Claudius, Hamlet, Gertrude) refer to them frequently by the wrong names.