OK, figured it out (or at least it works, so correct me if a better way is available):
This method assumes logged in frontend users, not sure if it's possible for guests, have not tested that. Might give permission errors.
Let's say, we have a section message with id 2, containing an asset field called photos. This is the field in which we want to save all frontend uploaded images.
In your form template, do everything exactly as this doc page says. Beware of the fact that you're own fields input names should start with 'fields[myFieldHandle]', and default fields such as title and author should just have their handle as input name.
Also, make sure your form has enctype="multipart/form-data" in its tag. What you have now, should look like this:
<form action="" method="POST" enctype="multipart/form-data">
<input type="hidden" name="action" value="entries/saveEntry" />
<input type="hidden" name="sectionId" value="2" />
<input type="hidden" name="enabled" value="1" />
<input type="file" name="assets-upload" multiple />
<input type="submit" value="Make it work!" />
</form>
You'll notice that the file input field has 'assets-upload' as its name. You can either do this, or make your uploading mechanism change the field name to 'assets-upload' for you, because Craft assumes this name in the controller class you're about to use.
For my form, I used the excellent Jquery File Upload plugin, which starts to do its work once files are selected in the file input field. I'm sure any other plugin could do the same. Make sure the plugin uploads the files to Craft's assets/uploadFile controller for them to be processed. The only thing this controller needs, is a folderId (the id of the asset folder the assets should be copied to). So, this is what the upload plugin needs:
$('#assets-upload').fileupload({
url: '{{ url(actions/assets/uploadFile) }}',
dataType: 'json',
formData: [{ name: 'folderId', value: yourfolderId}],
});
By now, you should be able to have your plugin send one or more assets to Craft's controller. Use firebug or Chrome's devTools to see what is returned. If everything worked as it should, a json-string should be returned containing the fileId(s) of the uploaded file(s).
The only thing left to do then, is creating hidden input fields to tell Craft which assets to relate to this entry. What JavaScript should append to the form, is one or more instances of:
<input type="hidden" name="fields[photos][]" value="yourFileId" />
Example, using the 'done' callback function in JQuery File upload:
...
done: function (e, data) {
if(data.result.success) {
var fileId = data.result.fileId;
$(this).after('<input type="hidden" name="fields[photos][]" value="' + fileId + '" />');
}
},
...
Submit your form, and see if it works. It should. If not, use the errors Craft returns to solve your problems (quite possibly permission-related).
Final note: My asset field is set to create a different file folder for each entry. In this case, I created a temporary folder and used its ID in the frontend form (because the folder is only created once the entry is saved). Craft will copy the assets to the right place and clean out this temp folder on saving the entry.