Hi, that's a pretty good and useful feature. I don't think that this feature (or lack of feature without JS) fulfills the criterias of functionality that should degrade: Search is currently not possible with or without JS; so the new feature is merely a progressive enhancement. That being said, searching the permissions (or the entire admin area for that matter) would be another useful feature request; but it certainly does not block this patch from getting in.
You have to do a bit more work than that but not much. I'm going to implement it for the modules page next, but that's going to be after this goes in.
Please do it in a generic way (e.g. you can mark tables as "filterable", like you can mark a table as "sticky table headers"). That way, we can save a lot of JS code. Konstantin