First, let me clarify that my answer refers to a purely anarchist society. Most libertarians are not anarchist, and tend to leave criminal-justice to state monopoly. The main difference between libertarian and current society is a great reduction in the range of activities currently considered criminal, with the elimination of victimless crimes.
Not only would directly-victimless crimes such as drug consumption, prostitution or gambling (not to mention many forms of regulatory and bureaucratic violations) go away, but, with them, many violent crimes associated with conducting profitable activities "outside the law".
As for punishing criminals in an anarchic society:
So would there be prisons or a means of detaining physically dangerous criminals?
There would certainly be prisons, fulfilling several purposes:
1. Detaining physically dangerous criminals
2. Detaining people from fleeing their responsibility to pay restitution
3. Providing uninsurable people with a secure environment within which to be productive
Or would it be either monetary payments or immediate execution?
Opinions on capital punishment vary. The preference is always to resolve criminal punishment through immediate monetary payment (together with subsequent non-coercive consequences, as discussed above), but in many cases, that wouldn't be possible. In those cases, extraction of monetary compensation would have to be prolonged, and, in a subset of those cases, require incarceration.
Who will pay for the prisons necessary to hold people awaiting trial, or would you not have trials?
Normally people awaiting trial, being considered innocent, cannot be held against their will. A broad exception to the rule is people carrying liability insurance, part of which may entitle their own insurance company to order them held before trial upon sufficient prima-facia evidence. Another exception involves uninsured people against which compelling evidence is immediately available (e.g. those caught in the act of a violent criminal action). In most cases, however, suspects would be summoned to defend themselves, even while those non-coercive measures (e.g. notification of their landlord, insurance company and employer, as well as dissemination of warnings to the local community) are taking place.
The cost of prisons used to hold people prior to trial will be born by the owners of restitution rights (normally insurance company), later recouped from the criminal (if convicted).
Who is paying for the judges etc. for that matter? How to handle an appeals process would raise a similar issue.
There can be various models for payments. Ultimately, the cost of criminal proceedings is born by the criminal if convicted, but the accuser (normally an insurance company) otherwise.
Free men are not equal and equal men are not free.
Government is not the solution. Government is the problem.