There isn't much useful documentation about using BIND for dynamic DNS, and I'm attempting to fix that situation by providing some here. This document assumes a general understanding of DNS.

Prerequisites

This document assumes that you are running a nameserver yourself. This means that you must have at least one static IP address for your domain. If you have no static IP addresses (such as if you are using DHCP with a cable modem), look at dyndns.com, who provide a solution that may be more along the lines of what you're looking for.

These instructions also assume a recent version 8 bind (as of this writing, you shouldn't be running anything but 8.2.3 anyway, or your machine will be 0wn3d by a script-kiddie with too much time on his hands in short order.)

Basics

named.conf

Let's suppose you'd like to set up a subdomain within your domain for all dynamic entries, to keep the clutter down. (I strongly recommend this, as opposed to simply allowing dynamic updates to your root domain. You can use cname entries where appropriate to link foo.domain.tld to foo.dynamic.domain.tld) You'd do it with an entry in named.conf which looks something like the following:
zone "dynamic.yourdomain.com." {
    type master;
    file "yourdomain.dynamic";
    allow-update {localhost; };
};
The file name is, of course, entirely a matter of personal preference, and you should follow whatever convention you are currently using. The allow-update line controls which machines can make updates - in the example above, only local connections from the nameserver itself are allowed (we'll cover allowing remote connections later).

Then, you'll need to create the file yourdomain.dynamic. It should look something like this:

dynamic.yourdomain.com	900 IN  SOA	yourdomain.com.  root.yourdomain.com.
(
	1	;serial
	900	;refresh
	1800	;retry
	691200	;expire
	900	;fail
)

    900	    IN	    NS	    nameserver.yourdomain.com.
Note, particularly, the low refresh time. This is presumably what you want, because by nature of the fact that updates are being made dynamically, you don't want answers cached for long. 900 seconds is 15 minutes; you can use a lower value (perhaps one or two minutes) if you consider it more appropriate.

Also note that the serial number doesn't obey the common YYYYMMDDRR convention. This is because it will be automatically incremented by BIND every time there's an update, and trying to follow the usual convention would be nothing but an exercise in futility. (This is one of the reasons it's desireable to have a separate dynamic subdomain.)

Remember to kill -HUP named after making these changes. You might also want to look in your syslogs after doing so to make sure there were no errors with the new configuration and/or domain.

nsupdate

To actually make an update, you'll use the command "nsupdate". Note that, with the configuration given above, you must run the command from the nameserver itself. If you're running nsupdate interactively, you'd do something like:
nsupdate
> update add foo.dynamic.yourdomain.com 900 A 1.2.3.4
> ^D

Note that the explicit TTL for the record must be specified; nsupdate exits with an error if you leave it out.

To confirm what you've done, nslookup the entry you just added, and confirm that it's present. If it's not, look in the syslogs for potential errors from named.

What named does

If you look in the directory where you keep your configuration files after making a dynamic update, you'll find that there's a file called "yourdomain.dynamic.log" (where yourdomain.dynamic is actually whatever you called the file for your dynamic subdomain). This file contains a record of all the dynamic updates which have been performed. It shows the hosts from which the update requests came, their contents, and changes such as increments of the serial number.

When named exits, the current state of the dynamic domain is written to the original file ("yourdomain.dynamic", in this example), overwriting the version which you manually created. This is a significant departure from named's normal behaviour, which never writes anything to the zone files for master domains. It is important to keep this in mind in selecting the location of the dynamic zone file.

Remote Updates

So, you've got your dynamicly-updatable subdomain running smoothly, but it isn't doing you much good, because you can update it only from the name server itself. You can allow updates from other fixed IP addresses by adding them to the allow-updates option, but that probably isn't what you want, because if you're using dynamic updates in the first place, you very likely don't know what IP you'll be using.

There is, happily, a solution, and this solution is to use keys for authentication. First, you'll need to generate the keys:

dnskeygen

Change to whichever directory you want the keys to be put in, /var/named/keys is a common choice, but is by no means required. Then, use the dnsgenkey command to actually generate the key. As an example, you could do something like:
dnskeygen -H 128 -h -n testkey
This will create two files in the current directory containing information about the key in question; you can see the dnskeygen manpage for more details about this step.

named.conf revisited

Once you've generated the key, you'll need to alter named.conf to use it. This would cause your named.conf to look something like this:

key testkey
{
    algorithm HMAC-MD5;
    secret "xxxxxxxx==";
};

zone "dynamic.yourdomain.com." {
    type master;
    file "yourdomain.dynamic";
    allow-update {key testkey; };
};
The "xxxxxxxx==" in the example above should be replaced by the actual key, which can be taken from either of the files generated by dnskeygen. Note that if there are any people with logins on the nameserver who should not have the ability to update the zone, it is necessary to remove read permissions from named.conf and the files generated by dnskeygen.

nsupdate revisited

To use nsupdate with the new key, you'll need to use the -k option. A sample command would look something like this:
nsupdate -k /var/named/keys:testkey.
The first part of the argument to the -k option is the directory in which the key is stored; the second is the key name. Note the trailing period; this is essential for nsupdate to find the key. (also note that it is the *.key file, and not the *.private file, which is used by nsupdate).

You can then proceed to use nsupdate normally. Obviously, a copy of the key must be transferred to any machine which should be able to perform dynamic updates to the name server.

Vagaries of nsupdate

nsupdate has some interesting features which allow you to make updates contingent on the current state; these are described in its manpage quite adequately, however, so I won't repeat the description here.

nsupdate also has some quirks and peculiarities which might trip you up, however, and those I will mention. The syntax is rigidly fixed; as mentioned above, the TTL field cannot be left out of an addition. Also, nsupdate provides no information about whether or not your operation has succeeded - you must simply check afterwards and see. It is possible to feed input to nsupdate from stdin, and you might want to do this if you're using it in a script. Be warned, however, that there must be a blank line at the end of nsupdate's input - if it is absent, nsupdate will exit without even attempting to contact the nameserver.

nsupdate is a young program, and presumably its robustness will increase with time. (it may no longer have the aforementioned limitations by the time you read this). For now, though, keeping these things in mind may save you some aggravation.