How much deposit do landlords ask for?

Usually one month's rent as a refundable deposit (kaucja), plus the first month's rent upfront. Occasionally two months.

Are bills included in the rent?

Sometimes for studios; usually bills (czynsz administracyjny, utilities) are extra. Always confirm what the advertised price includes.

Where to search, what deposits and fees to expect, the typical lease, and the documents a landlord will ask for.

OLX.pl — the most popular flat listing site.
Otodom.pl — real-estate portal, more agency listings.
Nieruchomosci-online.pl, Adresowo.pl.
Facebook groups ("Wynajmę mieszkanie [city]").
Real-estate agencies (biuro nieruchomości) — they charge a fee, usually one month's rent, sometimes paid by the landlord.

Rent (czynsz najmu) — the headline price.
Czynsz administracyjny — building maintenance fee, often separate.
Utilities — water, heating, electricity, internet. Varies sharply by apartment size, heating type, and occupancy; confirm what the advertised price includes.
Deposit (kaucja) — commonly one month as a market custom; for occasional leases capped at six months by law. Refundable.

The standard residential contract is an umowa najmu (lease). Do not call it umowa dzierżawy — that is a different (typically agricultural/ commercial) contract.
A special form is the najem okazjonalny (occasional lease): it requires a notarial declaration from the tenant and an alternative address, and gives the landlord faster eviction. Ask which type you are signing.
For occasional leases the statutory deposit may not exceed six times the monthly rent and must be returned within one month after you vacate, after lawful deductions.
Notice depends on the contract, term, and payment period. For a monthly, indefinite lease the Civil Code default is generally one month at the end of a calendar month, subject to the contract and tenant-protection law.
Check: who pays repairs, subletting rules, rent-indexation clause, and whether registration at the address is supported (a lease is evidence of legal title for zameldowanie).

Passport/ID.
Proof of income or employment.
A PESEL and residence permit are not generally required to sign a private lease; requirements vary by landlord.
Occasionally a guarantor (poręczyciel) for students.

Inspect in person; photograph defects on move-in.
Sign an inventory (protokół zdawczo-odbiorczy).
Verify the landlord's ownership/title and identity before paying.
Pay by bank transfer to have a record.
Never pay before viewing the property and signing — beware listings asking for cryptocurrency, foreign transfers, or unusually large advance payments.