I just added a new sample to the documentation that ships with the ServiceAPI.  In the mean-time here it is, the two step process to first upload a file and then use it to create a new Rendition on a new Record.

You could also use Record.FilePath to use the uploaded file to create the electronic document for the Record itself.

FileInfo fi = new FileInfo("c:\\junk\\test.pdf");

var fileResponse = client.UploadFile(fi, System.Web.MimeMapping.GetMimeMapping(fi.Name));

Record rec = new Record();
rec.RecordType = new RecordTypeRef() { Uri = 2 };
rec.Title = "test";

rec.ChildRenditions = new List();

rec.ChildRenditions.Add(new RecordRendition()
{
    TypeOfRendition = RenditionType.Longevity,
    FromFileName = fileResponse.FilePath,
    Description = "my PDF rendition"
});

FileInfo mainFile = new FileInfo("c:\\junk\\test.docx");

var response = client.PostFileWithRequest(mainFile, rec);

foreach (Record record in response.Results)
{
    Console.WriteLine(record.Title);
}