Doing that on Windows

Although this question focuses on Linux, where personally I would go with the easy LD_PRELOAD method as outlined in other answers, Windows knows a similar mechanism that in fact has been abused in the more recent past (also see alternative approaches below). I used that method to "crack" one dongle system.

Enter ...

DLL placement (aka preloading, aka hijacking) attacks

The name has been given to the method fairly recently when it turned out that placing DLLs on remote shares and then navigating to shares in, say a media player, would result in the media player loading the remote DLL instead of a local version. This is by design. Changing it now would break hundreds if not thousands of applications.

This has been addressed by Microsoft in certain ways, although the only real solution is proper implementation on the application side. But then, many developers haven't even grasped NT security even though we have to deal with it ever since Windows 2000 became the first consumer OS based on the NT platform.

What does it have to do with your described goal?

Adding functionality doesn't necessarily imply that you patch the executable on-disk. You can also do it in memory.

How can you leverage it?

Whenever an application uses a DLL, and you can tell the load order with Dependency Walker or under a debugger, you can pick one of the DLLs it imports and replace that (in its current location) or placing another DLL in a path that precedes the existing DLL in the load order.

An alternative method is to change the name of the imported DLLs. In rare cases (well known DLLs, for example) this is the only viable method to load an alternative DLL and may still fail for certain special cases.

Limitations

If the used DLL exists in the first location in the DLL search order, you'll literally have to replace the file on disk, unless you rename the import as briefly mentioned above.

Implementations

A manual approach can be used for DLLs with only few exported symbols. The easiest would be to create a module definition file from the the DLL and from that create a DLL with only function forwarders. This way your placed DLL would get loaded already and would simply pass through the calls.

However, this approach will fail with exported variables (as opposed to functions).

Here's a simple Python script based on pefile which I wrote for another answer over at StackOverflow:

import os
import sys
import re

def main(pename):
    from pefile import PE
    print "Parsing %s" % pename
    pe = PE(pename)
    modname = os.path.basename(pename)
    libname = re.sub(r"(?i)^.*?([^\\/]+)\.(?:dll|exe|sys|ocx)$", r"\1.lib", modname)
    defname = libname.replace(".lib", ".def")
    print "Writing module definition file %s for %s" % (defname, modname)
    f = open(defname, "w") # want it to throw, no sophisticated error handling here
    f.write("LIBRARY %s\n\n" % modname)
    f.write("EXPORTS\n")
    numexp = 0
    for exp in pe.DIRECTORY_ENTRY_EXPORT.symbols:
        if exp.name:
            numexp += 1
            f.write("\t%s\n" % exp.name)
    print "Wrote %s with %d exports" % (defname, numexp)
    print "\n\nUse this to create the export lib:\n\tlib /def:%s /out:%s" % (defname, libname)

if __name__ == '__main__':
    if len(sys.argv) != 2:
        sys.stderr.write("ERROR:\n\tSyntax: fakelib <dllfile>\n")
        sys.exit(1)
    sys.exit(main(sys.argv[1]))

You could adjust it to create function forwarders instead of a simple module definition with exported names.

So this way you can shuttle your code into the target application and go from there.

Alternative approaches

Instrumentation and hooking have been mentioned already. Detours is an often mentioned example of hooking with an inconvenient EULA for most practical purposes. Refer to the existing answers for this kind of approach.

You can also use the AppInit_DLL registry value to inject a DLL early on. Or you could write a little launcher with a debugger loop and use Image File Execution Options to have your target launch your debugger first. A debugger can also influence the DLL loading or simply intercept - conveniently - calls at the boundary between executable and DLLs.

Trivia: this (Image File Execution Options) is how Process Explorer replaces Task Manager when you choose the option inside Process Explorer.

You'll notice how you can sort these approaches into the categories Ed McMan mentioned in his answer already. However, I'll leave that as an exercise to the reader :)