If you are totally new to AJAX (which stands for Asynchronous Javascript And XML), the AJAX entry on wikipedia is a good starting point:
Like DHTML and LAMP, AJAX is not a technology in itself, but a group of technologies. AJAX uses a combination of:
- HTML and CSS for marking up and
  styling information.  
- The DOM
  accessed with JavaScript to
  dynamically display and interact with
  the information presented.
- A method
  for exchanging data asynchronously
  between browser and server, thereby
  avoiding page reloads. The
  XMLHttpRequest (XHR) object is usually
  used, but sometimes an IFrame object
  or a dynamically added  tag is
  used instead.
- A format for the data
  sent to the browser. Common formats
  include XML, pre-formatted HTML, plain
  text, and JavaScript Object Notation
  (JSON). This data could be created
  dynamically by some form of
  server-side scripting.
As you can see, from a pure technological point of view, there is nothing really new here. Most of AJAX parts were already there in 1994 (1999 for the XMLHttpRequest object). The real novelty was to use these parts together as Google did with GMail (2004) and Google Maps (2005). Actually, both sites contributed heavily to the promotion of AJAX.
A picture being worth a thousand words, below a diagram that illustrates the communication between the client and the remote server, as well as the differences between the classic and the AJAX-powered applications:

For the orange part, you can do everything by hand (with the XMLHttpRequest object) or you can use famous JavaScript libraries like jQuery, Prototype, YUI, etc to "AJAXify" the client-side of your application. Such libraries aim to hide the complexity of JavaScript development (e.g. the cross-browser compatibility), but might be overkill for a simple feature.
On the server-side, some frameworks can help too (e.g. DWR or RAJAX if you are using Java), but all you need to do is basically to expose a service that returns only the required informations to partially update the page (initially as XML/XHTML - the X in AJAX - but JSON is often preferred nowadays).