Short answer:

• Plugins do not modify existing files, they hook into WordPress via an exposed API.
• Plugins can modify database schema.
• Plugins don’t have to uninstall cleanly.

Plugin Hooks

Plugins hook into WordPress at specific point exposed by the WordPress core.

http://codex.wordpress.org/Plugin_API

As an example, the function get_option() reads a site option from the database. Before any real action is taken inside this function, WordPress calls apply_filters( 'pre_option_' . $option, false ). Given an option foobar, a plugin could override this option’s true value with the following code:

function override_foobar( $unused ) {
    return 'My custom value.';
}
add_filter( 'pre_option_foobar', 'override_foobar' ); // add_filter(hook, function)

See also http://adambrown.info/p/wp_hooks/.

Plugins modifying the database

Plugins have the ability to modify the database, assuming the WordPress database user still has that permission. Some of the more complex plugins add their own tables. It’s possible that a plugin could modify core tables, and hopefully they would do this responsibly and in a way that doesn’t break things if the plugin is removed.

This has to be examined on a plugin-by-plugin basis.

Uninstalling plugins

The deactivate_plugins() function calls the action do_action( 'deactivate_' . trim( $plugin ) ). A plugin should hook to this action if specific things need to happen when the plugin is deactivated. In my experience few plugins do a lot of deactivation cleanup, ie. putting their settings in cold storage in case they are activated again.