Q:

Is it possible to have Sitecore add an underscore or other custom symbol instead of a space to media library names, so that instead of "trees jpg" it would be "trees_jpg"?

A:

Yes, this is possible. To do so, override Sitecore.Data.Items.Item CreateFromStream method which puts the file in the database. There is a possibility to change filenames which are stored in the database via MediaCreatorOptions options:
public override Sitecore.Data.Items.Item CreateFromStream(System.IO.Stream stream, string filePath, MediaCreatorOptions options);
Follow the steps below to change the filenames:

Hook the object defined as a creator for the MediaManager using the code below:

using System;
using System.Collections.Generic;
using System.Text;
using Sitecore.Events.Hooks;
using Sitecore.Resources.Media;
using ReplaceSpaceByUnderstore;

namespace HookReplace
{
    class HookReplaceUnderscore : IHook
    {
        public void Initialize()
        {
            MediaManager.Creator = new CustumMediaCreator();
        }
    }
}

Use the following code as a CustumMediaCreator:

1. Sample Code

using System;
using System.Collections.Generic;
using System.Text;
using Sitecore.Resources.Media;
using Sitecore.IO;
using System.IO;
namespace ReplaceSpaceByUnderstore
{
    public class CustumMediaCreator : MediaCreator
    {
        public override Sitecore.Data.Items.Item CreateFromStream(System.IO.Stream stream, string filePath, MediaCreatorOptions options)
        {
            string _filePath = FileUtil.GetParentPath(options.Destination);
            string _fileName = Path.GetFileNameWithoutExtension(filePath);
            string _fileExt = FileUtil.GetExtension(filePath);
            options.Destination = _filePath + "/" + _fileName + "_" + _fileExt;
            return base.CreateFromStream(stream, filePath, options);
        }

    }
}

Include your hook into the <hooks> section of web.config: