Got it figured out, turns out you just use ContentVersion to upload a File:
// ContentVersion is how you upload a file!
ContentVersion version = new ContentVersion();
version.Title='Mah File';
version.PathOnClient = 'C:\\mahfile.txt';
version.VersionData = Blob.valueOf('DummyFile');
insert version;
// After you insert the ContentVersion object, a base 'ContentDocument' is established
// The ID of the ContentDocument is what you need to attach the file to the Chatter post.
version = [SELECT ID,ContentDocumentId FROM ContentVersion WHERE ID=:version.id];
// Form a basic post attached to our own feed.
ConnectApi.FeedItemInput feedItem = new ConnectApi.FeedItemInput();
feedItem.subjectId = 'me'; // This can also be an objectID to post the file to.
// Now connect the feeditem to our already uploaded file.
feedItem.capabilities = new ConnectAPI.FeedElementCapabilitiesInput();
feedItem.capabilities.files = new ConnectAPI.FilesCapabilityInput();
feedItem.capabilities.files.items = new List<ConnectAPI.FileIdInput>();
ConnectAPI.FileIdInput attachFile = new ConnectAPI.FileIDInput();
//**** Here is where we attach the specific file to the post!
attachFile.id = version.contentDocumentid;
feedItem.capabilities.files.items.add(attachFile);
// Execute the posting
ConnectApi.FeedElement feedElement = ConnectApi.ChatterFeeds.postFeedElement(Network.getNetworkId(), feedItem);
In the end though, I ditched the ConnectAPI and used the code below. Seemed more straightforward to me and works in unit tests. (The ConnectAPI requires unit tests to use SeeAllData=true which is a deal breaker for me.)
// Upload the file
ContentVersion version = new ContentVersion();
version.Title='Mah File';
version.PathOnClient = 'C:\\mahfile.txt';
version.VersionData = Blob.valueOf('DummyFile');
insert version;
// Insert a simple post
FeedItem post = new FeedITem();
post.body = 'File Upload';
post.ParentID = UserInfo.getUserID();
insert post;
// Associate the file with the post
FeedAttachment postAttachment = new FeedAttachment();
postAttachment.FeedEntityId = post.id;
postAttachment.Type = 'Content';
postAttachment.RecordId = version.id;
insert postAttachment;