Simply PUT the below content to the resource URI of a workitem, e.g.
https://clm405:9443/ccm/resource/itemName/com.ibm.team.workitem.WorkItem/43

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:oslc_cm="http://open-services.net/ns/cm#"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:rtc_ext="http://jazz.net/xmlns/prod/jazz/rtc/ext/1.0/"
    xmlns:oslc_cmx="http://open-services.net/ns/cm-x#"
    xmlns:acp="http://jazz.net/ns/acp#"
    xmlns:rtc_cm="http://jazz.net/xmlns/prod/jazz/rtc/cm/1.0/"
    xmlns:oslc="http://open-services.net/ns/core#"
    xmlns:oslc_pl="http://open-services.net/ns/pl#" >
  <rdf:Description>
    <rtc_cm:com.ibm.team.workitem.linktype.blocksworkitem.dependsOn rdf:resource="https://clm405:9443/ccm/resource/itemName/com.ibm.team.workitem.WorkItem/61"/>
     <rtc_cm:com.ibm.team.workitem.linktype.blocksworkitem.dependsOn rdf:resource="https://clm405:9443/ccm/resource/itemName/com.ibm.team.workitem.WorkItem/62"/>
 </rdf:Description>
</rdf:RDF>

In this example, the links are established so that WI 43 "Depends On" WI 61 and WI 62.
Note that the same link type will be overwritten, so if you want to "add" work items to the same link type, you need to add the existing work items in the PUT payload. For example, if later on you want to link WI 63 so that WI 43 "Depends On" WI 63 as well, you need to put all three work items in the PUT payload.
To find out what link types are available for the work item type, check the instance shape of the work item type, such as
https://clm405:9443/ccm/oslc/shapes/workitems/_RsxIUGLBEeOj4c1n9GOJ3Q (this is Task in my system)
You can get the instanceShape URL when you GET a work item of this type (look for <oslc:instanceShape>).