Data
Obviously, a computer requires data  what else is it to compute? In this case, we'll put all data in binary: two becomes 10, four becomes 100, ten becomes 1010, twenty becomes 10100. Representing binary with black holes (nice large ones, mind you, that won't go evaporating on us) is relatively simple: all you need is a string of spaces, uniformly seperated, each of which either does or does not contain a black hole.
With each dot representing a black hole and each o representing an empty space, two hundred and fifteen (or 11010111) would look like this: ..o.o...  two black holes, then a space, then a black hole, then a space, then three black holes.
Gates
Every computer can be thought of as built from 3 simple elements: OR gates, AND gates, and NOT gates.
OR
Our OR gate will take 2 binary numbers as its input, comparing them with each other digit by digit, and will spew out a 1 in a particular place if either digit is a 1 and a 0 if neither is: for example, if provided with 1100101 and 0101001, it will output 1101101.
Construction is fairly simple  create a gravitational well or field of force that channels the 2 streams of black holes toward each other, until they are side by side and parallel, like so: =, ensuring that the digits line up. Once the corresponding digits of the two streams become much closer to each other than they are to the preceding and following black holes in their own streams, gravity takes over:
 If both corresponding digits have black holes in them, the holes will merge into a new hole  1 and 1 combine to output 1.
 If only 1 of the corresponding digits has a black hole in it, that black hole will still be there, filling the space. 0 and 1 combine to output 1.
 If neither of the corresponding digits has a black hole in it, there will still be an empty space. 0 and 0 make 0.
(If your mental picture isn't working properly, if you're concerned the speed and direction of each black hole changing or about black holes gobbling up holes they're not meant to, keep in mind that the spaces between the black holes dwarf the size of each hole by many, many orders of magnitude.)
NOT
Our NOT gate will take a single binary number and convert it to its opposite  every 0 becomes a 1, every 1 a 0. 1100101 turns into 0011010.
For this we need a reference string of arbitrary length  which is to say, a countinuous parade of evenly spaced black holes (think of it as infinitely long if you think that's cool). Perpindicular to this we will place our input, again calibrating the speed and placement of each stream such that the black holes line up. The output will be what was formerly the reference stream, after it has passed through the binary number input: if the input is a 1 (a black hole), the two will merge and their combined momentum will carry them away in another direction, leaving a space (a 0); if the input is a 0 (an empty space), the reference black hole will continue along its path, becoming a 1.
. _______the rest of the input, not yet passed through the gate
.
.
..... . . _________0s have become 1s
 .
 . ________1s are carried away, leaving 0s

 .
Reference stream
AND
Our AND gate will take 2 binary numbers as its input, comparing them with each other digit by digit, and will spew out a 1 in a particular place if both digits are 1 and a 0 either of them is a 0: for example, if provided with 1100101 and 0101001, it will output 0100001.
Implementation is simple: the two numbers are simply passed through the OR gate, one having first been through the NOT gate (if I have a coat or no hat, I have both a coat and a hat, or neither).
These three gates are all we need  from them alone, it is possible to assemble a fully functioning computer. It will be very slow, of course, but will have a tremendous time frame within which to operate: the Black Hole era will last almost 10^{100} years.
Okay, what the fuck are you smoking?
Excellent question (especially considering the current quest). This whole system is taken from Chapter 4 of the cool and informative The Five Ages of the Universe, by physicists Fred Adams and Greg Laughlin. Their reasoning:
Currently, our universe is interesting: there are many types of particles interacting in complex ways, giving rise to interesting things like people, who posses interesting things like minds. This state of affairs is not eternal, however: in 10^{40} years, almost all protons will have died; there will be no galaxies, no stars, no planets, no specks of dust, no atoms; the only objects to survive will be those protected by an event horizon, and there won't be much interaction there  black holes have no hair.
The question, therefore, becomes "Can interacting black holes create complexity sufficient for intelligence, as interacting atoms do today?" In designing their hypothetical computer, Adams and Laughlin haven't answered that, but they have created a compelling proof of concept, shown that though engineering is a challenge (so to speak), there are no fundamental conceptual difficulties. From the chapter's fictional introduction:
Although Bob's concerns tended to be of a flatly practical nature, there were members of his species who were trying to understand the properties of the universe during its first 10^{40} years, "those almost unimaginably brief moments after the big bang." Particularly fashionable was a wild conjecture that highly complex structures might have been based on the interaction of electrons with protons and neutrons. The existence of protons and neutrons, exotic shortlived particles that had long since decayed away, was enthusiastically embraced by the more adventurous physicists of the time, and simultaneously denounced as "rampant speculation" by those cut from a more conservative cloth.
A clarificaton, since there seems to be a bit of confusion:
The Five Ages of the Universe has gotten great reviews everywhere I've seen, from physicists and critics alike; its science is sound. The popular conception of a black hole is that of a cosmic vacuum cleaner, but that isn't entirely accurate  from afar (and discounting emissions, etc.), a black hole acts like any other object; the only difference is that the entire mass is at the very center, so it is possible to get very close to it. If the sun were to be suddenly replaced by a black hole of the same mass, the Earth's orbit would be unchanged.