Does anyone know how to create a search that gives a list of customers by their state?

define "by their state" - what happens if a customer is in more than 1 state in your ideal report? repeated more than once?

I'm looking for a list of customers grouped by their state. I can create the search based on customer transactions but have been struggling to find a way to create one based just on customers.

create a customer saved search. Then add either their BILLING or SHIPPING state. Add a filter for the same. If you have more addresses defined you will need to determine how to select the appropriate address to use for the group by state. To make this dynamic you could add values in the Summary column on the results page. Group by the state and then count by the customer number. This will show you a list by states with the number of customers in each state. If you click on a single state name, you will see the details for each customer in that state.

You should be able to set up a Client based search and use STate/Province from the Address Fields, Shipping Address fields or Billing Address Fields as criteria. But as Kevin mentioned, that could certainly run into problems if a customer has multiple states or your criteria for setting up addresses isn't consistent.