<p>What is the best way to upload a file to a Document Library on a SharePoint server through the built-in web services that version WSS 3.0 exposes?</p>

<p><strong>Following the two initial answers...</strong></p>

<ul>
<li><p>We definitely need to use the Web Service layer as we will be making these calls from remote client applications.</p></li>
<li><p>The WebDAV method would work for us, but we would prefer to be consistent with the web service integration method.</p></li>
</ul>

<p><Blockquote>
There is additionally a web service to upload files, painful but works all the time.
</Blockquote></p>

<p>Are you referring to the “Copy” service? 
We have been successful with this service’s <code>CopyIntoItems</code> method. Would this be the recommended way to upload a file to Document Libraries using only the WSS web service API?</p>

<p>I have posted our code as a suggested answer.</p>

From a colleage at work:
Lazy way: your Windows WebDAV filesystem interface. It is bad as a programmatic solution because it relies on the WindowsClient service running on your OS, and also only works on websites running on port 80. Map a drive to the document library and get with the file copying.
There is additionally a web service to upload files, painful but works all the time.
I believe you are able to upload files via the FrontPage API but I don’t know of anyone who actually uses it.