In my practice, agile projects are set up and budgeted the same way as the regular ones. We have business case / high-level scope, based on this we make a preliminary estimation for cost and schedule, check it against our past experiences (or past project metrics), and document it in the project charter.
Most agile methods do not cover the entire project lifecycle, so from high level (say, from top management level) projects that are agile are just the same as projects that are executed in a more traditional way. Of course, for expectation management reasons it is good to communicate the methodology (so they will understand and even anticipate scope changes).
There may be one significant difference when estimating agile projects: it is usually a very bad setup if you only have time / budget for mandatory requirements, so either include some optional ones in the initial scope, or have a big (30-40% or even more) reserve for extra features that may come later. This way your team (product owner, etc) will be able to handle scope changes in a flexible way.