Leider sind Verknüpfungen eine sehr Microsoft-spezifische Sache (zumindest in der Form, in der sie in XP sind – was ich nach kurzer Recherche gelesen habe, gibt's ab Vista echte Symbolic Links), die daher in Java afaik nicht wirklich unterstützt ist. Wenn du einen Command-Line-Befehl findest, mit dem du eine Verknüpfung erstellen kannst, könntest du den dann mit
Code (Java): 
Runtime.getRuntime().exec(command);

ausführen. (Natürlich, nachdem du geprüft hast, dass du auch wirklich unter Windows bist, und nachdem du die Argumente escapet hast, falls sie User-Input in irgendeiner Form enthalten.)
Allerdings habe ich bei einer kurzen Suche keinen solchen Befehl gefunden. :-/

Hier zwei relevante Frage-Threads, die ich gefunden habe:
Creating shortcuts from Java code
Creating shortcuts from the command line

Falls alles andere nicht hilft, könntest du noch immer anschauen, wie das Binär-Format von Verknüpfungen ausschaut, und die notfalls auf diese Weise selber erstellen. So kompliziert wird das Format ja wahrscheinlich nicht sein. Weiß aber nicht, ob dir das die Mühe wert ist.